Build the lexicographically smallest number that matches a given sequence of increasing and decreasing constraints.
Given a pattern string made up of the characters I and D, construct the smallest possible number using the digits 1 to 9 without repetition such that the generated sequence satisfies the pattern.
I means the next digit must be greater than the previous digit.D means the next digit must be smaller than the previous digit.You must use exactly pattern.length + 1 digits, and each digit can be used at most once. Return the lexicographically smallest valid number as a string.
pattern consisting only of characters I and D.n = pattern.length.n + 1 distinct digits from 1 to 9.1 <= pattern.length <= 8pattern[i] is either I or D1 to 9 and cannot repeatExample 1
Input
pattern = "IIIDIDDD"
Output
123549876
Explanation
The sequence 1 < 2 < 3 < 5 > 4 < 9 > 8 > 7 > 6 matches the pattern and is the smallest such number.
Example 2
Input
pattern = "DDD"
Output
4321
Explanation
A decreasing pattern requires each next digit to be smaller than the previous one, and 4321 is the smallest valid arrangement.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.