#2375
Construct Smallest Number From DI String
pupil · 390 · lc medium +24 · verified · 85.6% accepted · 1,659 likes · top 97%
Description
You are given a 0-indexed string pattern of length n consisting of 'I' (increasing) and 'D' (decreasing) characters.
Construct a 0-indexed digit string num of length n + 1 using digits '1' through '9' (each used at most once) such that:
- num[i] < num[i + 1] whenever pattern[i] == 'I'.
- num[i] > num[i + 1] whenever pattern[i] == 'D'.
Return the lexicographically smallest valid string num.
Example 1:
Input: pattern = "IIIDIDDD"
Output: "123549876"
Explanation:
At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].
At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].
Some possible values of num are "245639871", "135749862", and "123849765".
It can be proven that "123549876" is the smallest possible num that meets the conditions.
Note that "123414321" is not possible because the digit '1' is used more than once.
Example 2:
Input: pattern = "DDD"
Output: "4321"
Explanation:
Some possible values of num are "9876", "7321", and "8742".
It can be proven that "4321" is the smallest possible num that meets the conditions.
Code
1
2
3