PROBLEM LINK:
Author: ravikiran0606
Editorialist: ravikiran0606
DIFFICULTY:
EASYMEDIUM
PREREQUISITES:
RECURSION, BACKTRACKING
PROBLEM:
Given an integer N and a string S of length N. We need to generate a number with N+1 digits such that the following contraints holds true,

If the (i)'th character of the string is I, then (i)'th digit in the number > (i+1)'th digit in that number.

If the (i)'th character of the string is D, then (i)'th digit in the number < (i+1)'th digit in that number…

All the digits of the number are distinct and nonzero.
EXPLANATION:
In this question, its very easy to find one of the cases for 1 that for all N>=9, the answer is always 1 since there are only 9 nonzero distinct digits from 1 to 9. Thus we can find solution only if N<=8. If the length of the string is N, we need to generate a number with N+1 digits with the given contraint. We can solve this using recursion and backtracking by trying all possible combinations of digits of length N+1 with the given constraint and print the lexicographically smallest one. If no solution exists we can print 1. The expected complexity is O(9^{n}).
AUTHOR’S SOLUTION:
Author’s solution can be found here