Construct Smallest Number From DI String - Solution & Explanation

Problem Overview: You are given a string consisting of 'D' (decreasing) and 'I' (increasing). The goal is to build the smallest possible number using digits 1–9 without repetition such that the digits follow the pattern. For example, if the pattern contains D, the next digit must be smaller than the previous digit. The challenge is enforcing the pattern while keeping the overall number lexicographically smallest.

Approach 1: Greedy Approach with Stack (O(n) time, O(n) space)

This approach processes the pattern from left to right and uses a stack to temporarily store digits. Push numbers sequentially starting from 1. Whenever you encounter an 'I' or reach the end of the pattern, pop all elements from the stack and append them to the result. This reversal ensures that segments of 'D' automatically produce decreasing sequences while still using the smallest available digits. The key insight: delaying output until an increasing boundary lets you reverse the necessary portion to satisfy multiple consecutive D constraints.

This greedy strategy guarantees the smallest valid number because digits are assigned in increasing order and only reversed when the pattern forces a decrease. Each digit is pushed and popped once, making the algorithm linear. This is the most common interview solution and works well for patterns with long decreasing runs.

Approach 2: Construct from Left to Right (Greedy Pattern Handling) (O(n) time, O(1) extra space)

Another strategy builds the answer array directly while scanning the pattern. Start by filling the digits sequentially. When a 'D' segment appears, identify the full length of that decreasing run and reverse the corresponding portion of the result. For example, if the pattern contains DDD, the next four digits must form a decreasing sequence, so the digits assigned to that segment are reversed after placement.

This method relies on the same greedy observation: the smallest digits should appear as early as possible, but decreasing runs must be reversed to satisfy ordering constraints. Instead of using a stack, the algorithm manipulates segments directly. The logic stays simple and uses constant auxiliary memory.

Approach 3: Backtracking (O(9! ) worst case, O(n) space)

A brute-force method uses backtracking to generate permutations of digits 1–9 and check whether each permutation satisfies the DI pattern. Because the goal is the smallest valid number, the search can stop as soon as a valid candidate appears. While conceptually straightforward, the factorial search space makes this impractical for interviews. It mainly helps illustrate the constraint structure before applying a greedy optimization.

Recommended for interviews: The greedy stack solution is the expected answer. It demonstrates understanding of pattern constraints and efficient use of a greedy strategy with a stack. Explaining the brute-force backtracking approach first shows reasoning about the search space, but implementing the O(n) greedy method signals strong problem-solving skills.