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.
Imeans the next digit must be greater than the previous digit.Dmeans 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.
Input Format
- A string
patternconsisting only of charactersIandD. - Let
n = pattern.length. - Construct a sequence of
n + 1distinct digits from1to9.
Output Format
- Return a string representing the smallest valid number that satisfies the pattern.
Constraints
1 <= pattern.length <= 8pattern[i]is eitherIorD- Digits must be from
1to9and cannot repeat - At least one valid answer exists
Example 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
Unlock deeper context for this problem
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.