Construct Smallest Number From DI String — Solution
Construct Smallest Number From DI String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Construct Smallest Number From DI String is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Goldman Sachs interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Stack, Backtracking
- Asked at: Amazon, Google, Goldman Sachs
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string pattern of length n made of the letters 'I' (increasing) and 'D' (decreasing).
Build a string num of length n + 1 such that:
numuses only the digits'1'to'9', each digit 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 such string.
Example 1
Input: pattern = "DDI"
Output: 3214
Explanation: The first three digits must fall, then rise; `3214` is the smallest way to do that.
Example 2
Input: pattern = "IDID"
Output: 13254
Example 3
Input: pattern = "D"
Output: 21
Constraints
1 <= pattern.length <= 8pattern consists of only the letters 'I' and 'D'
Hints for Construct Smallest Number From DI String
Hint 1
If the pattern were all
Is, the answer would be1 2 3 …. What does a run ofDs do to that?Hint 2
A run of
kDs needsk + 1falling digits. Use the smallest unused digits for them, written in reverse.Hint 3
Push
i + 1onto a stack for each position; whenever the pattern saysI(or the string ends), pop the whole stack into the answer.
How to solve Construct Smallest Number From DI String
Start from the ascending sequence 1, 2, …, n + 1 and reverse each block that a run of Ds covers. A stack does those reversals on the fly.
Approach
- For
ifrom 0 ton, push the digiti + 1onto a stack. - If
i == norpattern[i] == 'I', pop every digit off the stack and append it to the answer. - Return the answer.
Why it works
Each maximal group of positions joined by Ds must be strictly decreasing, and consecutive groups are joined by an I. Using the digits in increasing order, each group receives the smallest digits still unused, placed in decreasing order — any smaller digit at the front of a group would have to be followed by an even smaller one that is already taken. The stack pushes the group's digits in increasing order and pops them in reverse exactly when the group ends at an I or at the end of the string. Digits 1 to n + 1 <= 9 always suffice.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Remember to flush the stack after the last position as well.
- A purely greedy "smallest unused digit" choice fails on
D: the first digit must leave room for the whole falling run. - The answer always uses exactly the digits
1..n+1.
Reference solution
Python
def smallestNumber(pattern: str) -> str:
out = []
stack = []
for i in range(len(pattern) + 1):
stack.append(str(i + 1))
if i == len(pattern) or pattern[i] == "I":
while stack:
out.append(stack.pop())
return "".join(out)Java
public static String smallestNumber(String pattern) {
StringBuilder sb = new StringBuilder();
Deque<Integer> stack = new ArrayDeque<>();
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()) sb.append(stack.pop());
}
}
return sb.toString();
}C++
string smallestNumber(string pattern) {
string out;
vector<char> st;
int n = pattern.size();
for (int i = 0; i <= n; i++) {
st.push_back((char)('1' + i));
if (i == n || pattern[i] == 'I') {
while (!st.empty()) { out += st.back(); st.pop_back(); }
}
}
return out;
}JavaScript
var smallestNumber = function(pattern) {
var out = "", stack = [];
for (var i = 0; i <= pattern.length; i++) {
stack.push(String(i + 1));
if (i === pattern.length || pattern[i] === "I") {
while (stack.length) out += stack.pop();
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms