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.
A highly efficient greedy approach can solve this problem in linear time. The strategy is to iterate through the digits 1, 2, ..., n+1 and use a stack to handle the formation of decreasing sequences. When we encounter an 'I', it signals that the preceding sequence of 'D's has ended. The numbers collected on the stack for this decreasing segment are then popped and appended to the result, which naturally reverses their order and satisfies the 'D' conditions.
Algorithm
- Initialize an empty result string (or
StringBuilder) and an empty stack. - Iterate with an index
ifrom 0 ton, wherenis the length of the pattern. This loop corresponds to then+1digits of the output number. - In each iteration, push the next available number,
i + 1, onto the stack. - If the current character
pattern[i]is 'I', or if we have reached the end of the pattern (i == n), it marks the end of a decreasing sequence. - At this point, pop all elements from the stack and append them to the result. This reverses the order of the numbers pushed for the segment, creating the required decreasing sequence.
- After the loop completes, the result string will hold the lexicographically smallest number.
Walkthrough
We process the pattern from left to right. We use a counter to generate digits 1, 2, 3, .... For each position in the output number, we consider placing the next smallest available digit. These digits are pushed onto a stack. A character 'I' in the pattern (or the end of the pattern) acts as a trigger. It finalizes the preceding block of numbers. This block might have been governed by 'D's, requiring a decreasing sequence. By popping the numbers from the stack, we get them in reverse order of how they were pushed. Since we pushed k, k+1, k+2, ..., popping gives ..., k+2, k+1, k, which is exactly the decreasing sequence needed. This ensures that for any segment, we use the smallest possible set of digits, and arrange them to be lexicographically minimal at the start of the segment.
import java.util.Stack; class Solution { public String smallestNumber(String pattern) { StringBuilder result = new StringBuilder(); Stack<Integer> stack = new Stack<>(); int n = pattern.length(); for (int i = 0; i <= n; i++) { stack.push(i + 1); if (i == n || pattern.charAt(i) == 'I') { while (!stack.isEmpty()) { result.append(stack.pop()); } } } return result.toString(); }}Complexity
Time
O(n), where n is the length of the pattern. Each number from 1 to `n+1` is pushed onto the stack once and popped from the stack once.
Space
O(n), where n is the length of the pattern. In the worst-case scenario (a pattern of all 'D's), the stack will store `n+1` elements.
Trade-offs
Pros
Optimal time complexity of O(n).
Simple implementation using a standard stack data structure.
Single-pass solution.
Cons
The logic might be slightly less intuitive to grasp initially compared to a direct reversal approach.
This is another optimal greedy approach that is very intuitive. The idea is to start with the lexicographically smallest possible permutation of the required digits, which is simply the sorted sequence '123...'. This sequence satisfies all 'I' (increasing) conditions. Then, we iterate through the pattern and fix the segments that need to be decreasing ('D'). A block of consecutive 'D's implies a strictly decreasing subsequence of numbers. We achieve this by reversing the corresponding segment in our initial '123...' string.
Algorithm
- First, create a candidate result string
resconsisting of digits '1' ton+1in increasing order (e.g., "1234" for a pattern of length 3). - This initial string already satisfies all 'I' conditions.
- Iterate through the
patternstring from left to right with an indexi. - If
pattern[i]is an 'I', do nothing as the condition is already met. - If
pattern[i]is a 'D', it marks the start of a decreasing segment. Find the end of this contiguous block of 'D's. Let's say it ends at indexj-1. - Reverse the substring of
resfrom indexitoj. - After reversing, update the loop counter
itoj-1to continue scanning from the end of the processed 'D' block. - The final
resstring is the answer.
Walkthrough
Let the length of the pattern be n. The result will have length n+1 and use digits from '1' to n+1 to be lexicographically minimal. We start with a StringBuilder or char[] initialized to "123...(n+1)". We then scan the pattern. When we encounter a block of k consecutive 'D's starting at index i, it means num[i] > num[i+1] > ... > num[i+k]. In our initial string, this segment is (i+1), (i+2), ..., (i+k+1). To satisfy the 'D's while keeping the numbers in this segment as small as possible, we must arrange these specific k+1 numbers in decreasing order. This is achieved by simply reversing this segment of the string. We repeat this for every block of 'D's in the pattern.
class Solution { public String smallestNumber(String pattern) { int n = pattern.length(); StringBuilder res = new StringBuilder(); for (int i = 0; i <= n; i++) { res.append((char)('1' + i)); } for (int i = 0; i < n; i++) { if (pattern.charAt(i) == 'D') { int j = i; while (j < n && pattern.charAt(j) == 'D') { j++; } reverse(res, i, j); i = j - 1; } } return res.toString(); } private void reverse(StringBuilder sb, int start, int end) { while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } }}Complexity
Time
O(n), where n is the length of the pattern. The nested loops still result in linear time because each character of the pattern and each digit of the result is processed a constant number of times.
Space
O(n) to store the result string. The reversal is done in-place, so it requires O(1) auxiliary space.
Trade-offs
Pros
Optimal O(n) time complexity.
The logic is very intuitive and easy to reason about.
Can be implemented with low overhead.
Cons
Requires a mutable string or character array to perform efficient in-place reversals.
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; } } }}class Solution {public: string ans = ""; string pattern; vector<bool> vis; string t = ""; string smallestNumber(string pattern) { this->pattern = pattern; vis.assign(10, false); dfs(0); return ans; } void dfs(int u) { if (ans != "") return; if (u == pattern.size() + 1) { ans = t; return; } for (int i = 1; i < 10; ++i) { if (!vis[i]) { if (u && pattern[u - 1] == 'I' && t.back() - '0' >= i) continue; if (u && pattern[u - 1] == 'D' && t.back() - '0' <= i) continue; vis[i] = true; t += to_string(i); dfs(u + 1); t.pop_back(); vis[i] = false; } } }};class Solution: def smallestNumber(self, pattern: str) -> str: def dfs(u): nonlocal ans if ans: return if u == len(pattern) + 1: ans = '' . join(t) return for i in range(1, 10): if not vis[i]: if u and pattern[u - 1] == 'I' and int(t[- 1]) >= i: continue if u and pattern[u - 1] == 'D' and int(t[- 1]) <= i: continue vis[i] = True t . append(str(i)) dfs(u + 1) vis[i] = False t . pop() vis = [False] * 10 t = [] ans = None dfs(0) return ansVideo 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.