Construct Smallest Number From DI String

Construct Smallest Number From DI String

What is this problem about?

The Construct Smallest Number From DI String interview question gives you a pattern string of length n consisting of 'I' (Increasing) and 'D' (Decreasing). You need to construct the lexicographically smallest string of length n+1 using digits '1'-'9' (each digit at most once) that follows the pattern.

Why is this asked in interviews?

Goldman Sachs and Google use the Construct Smallest Number From DI String coding problem to test greedy thinking and stack manipulation. While it can be solved with backtracking, the interviewer is usually looking for an O(N) greedy or stack-based approach that demonstrates a higher level of algorithmic efficiency.

Algorithmic pattern used

This problem follows the Backtracking, Stack, Greedy interview pattern. The stack-based greedy solution is particularly elegant:

1. Iterate through the pattern plus one extra step.
2. Always push the next available digit (1, 2, 3...) onto a stack.
3. If you encounter an 'I' (or reach the end of the pattern), pop everything from the stack and append it to your result string.
4. If you encounter a 'D', just keep pushing to the stack.

Example explanation

Pattern: "IDID"

1. Push 1. Pattern 'I' -> Pop 1. Result: "1".
2. Push 2. Pattern 'D' -> Stay.
3. Push 3. Pattern 'I' -> Pop 3, then 2. Result: "132".
4. Push 4. Pattern 'D' -> Stay.
5. Push 5. End -> Pop 5, then 4. Result: "13254".

This ensures that whenever we need to decrease, we reverse the order of the digits we just collected, which naturally provides the smallest possible values for the increasing sections.

Common mistakes candidates make

• Using Backtracking unnecessarily: Backtracking works but is O(9!) or O(P^N). The stack approach is much faster.
• Digit Re-use: Forgetting that each digit can only be used once.
• Lexicographical order: Failing to pick the smallest available digits at the start of the process.

Interview preparation tip

Problems involving "Increasing/Decreasing" patterns in strings are often solvable by a simple "Stack and Reverse" logic. If you need to reverse a trend, a stack is the most natural tool to hold the elements until the trend shifts.