Construct Smallest Number From DI String
You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.
A 0-indexed string num of length n + 1 is created using the following conditions:
numconsists of the digits'1'to'9', where each digit is used at most once.- If
pattern[i] == 'I', thennum[i] < num[i + 1]. - If
pattern[i] == 'D', thennum[i] > num[i + 1].
Return the lexicographically smallest possible string num that meets the conditions.
Example 1
Input
pattern = "IIIDIDDD"Output
"123549876"It can be proven that "123549876" is the smallest possible value satisfying all increasing and decreasing requirements, while using each digit at most once.
Example 2
Input
pattern = "DDD"Output
"4321"It can be proven that "4321" is the smallest possible value satisfying the decreasing pattern.
Constraints
- 1 <= pattern.length <= 8
- pattern consists of only the letters 'I' and 'D'.