Construct Smallest Number From DI String
MedPrompt
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"
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.
Constraints:
1 <= pattern.length <= 8patternconsists of only the letters'I'and'D'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion and backtracking to explore all possible permutations of digits that could form a valid number. It systematically builds the number from left to right, trying all possible valid digits at each position. To ensure the result is lexicographically the smallest, digits are tried in increasing order ('1', '2', '3', ...). The first valid number of length n+1 that is found is guaranteed to be the smallest possible one.
Algorithm
- Define a recursive function, say
findSmallest(currentNum, usedDigits), to build the number. currentNumis the string built so far, andusedDigitsis a boolean array to track used digits from '1' to '9'.- The base case for the recursion is when
currentNumreaches the required length (n + 1). Since we build the number by trying smaller digits first, the first complete number found will be the lexicographically smallest. We store it and stop further exploration. - In the recursive step, iterate through digits
dfrom '1' to '9'. - If
dhas not been used, check if it can be appended tocurrentNumbased on the last character ofcurrentNumand the corresponding character inpattern. - If the placement is valid, mark
das used and make a recursive call for the next position. - After the recursive call, backtrack by un-marking
das used to explore other possibilities.
Walkthrough
The core of this method is a backtracking function that constructs the output string num one digit at a time. We maintain a boolean array used to keep track of which digits from '1' to '9' have already been placed in num. The function attempts to fill the k-th position of num. It iterates through all unused digits d from '1' to '9'. For each d, it checks if placing it at num[k] would violate the condition imposed by pattern[k-1]. If pattern[k-1] is 'I', d must be greater than num[k-1]. If 'D', d must be smaller. If the condition is met, the function places d at num[k], marks it as used, and recursively calls itself to fill the (k+1)-th position. If the recursion successfully builds a full-length number, we have found our answer. If not, it backtracks by undoing the choice of d and trying the next available digit.
class Solution { String result = ""; int n; public String smallestNumber(String pattern) { this.n = pattern.length(); findSmallest("", new boolean[10]); return result; } private void findSmallest(String currentNum, boolean[] used) { if (!result.isEmpty()) { return; // Already found the smallest number, terminate early. } if (currentNum.length() == n + 1) { result = currentNum; return; } for (int i = 1; i <= 9; i++) { if (!used[i]) { if (currentNum.length() > 0) { char lastChar = currentNum.charAt(currentNum.length() - 1); char p = pattern.charAt(currentNum.length() - 1); if (p == 'I' && (lastChar - '0') >= i) { continue; } if (p == 'D' && (lastChar - '0') <= i) { continue; } } used[i] = true; findSmallest(currentNum + i, used); // If a result is found, we don't need to backtrack further from this path if (!result.isEmpty()) { return; } used[i] = false; // Backtrack } } }}Complexity
Time
O(k!) where k is the length of the output number (n+1). For the given constraints (n <= 8), this is at most O(9!), which is computationally expensive but feasible.
Space
O(n), where n is the length of the pattern. This is for the recursion stack depth and the `used` array.
Trade-offs
Pros
Guarantees finding the correct, lexicographically smallest solution.
It's a general approach that can be adapted for many constraint satisfaction and permutation problems.
Cons
Very high time complexity, making it impractical for larger constraints.
The number of states can be very large, leading to a deep and wide recursion tree.
Solutions
Solution
class Solution {private boolean[] vis = new boolean[10];private StringBuilder t = new StringBuilder();private String p;private String ans;public String smallestNumber(String pattern) { p = pattern; dfs(0); return ans; }private void dfs(int u) { if (ans != null) { return; } if (u == p.length() + 1) { ans = t.toString(); return; } for (int i = 1; i < 10; ++i) { if (!vis[i]) { if (u > 0 && p.charAt(u - 1) == 'I' && t.charAt(u - 1) - '0' >= i) { continue; } if (u > 0 && p.charAt(u - 1) == 'D' && t.charAt(u - 1) - '0' <= i) { continue; } vis[i] = true; t.append(i); dfs(u + 1); t.deleteCharAt(t.length() - 1); vis[i] = false; } } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.