LeetCode 2375 - Construct Smallest Number From DI String

The problem asks us to construct the lexicographically smallest number from a string pattern consisting of 'I' and 'D'.

leetcodemediumstringbacktrackingstackgreedy

LeetCode Problem 2375

Difficulty: 🟡 Medium
Topics: String, Backtracking, Stack, Greedy

Solution

Problem Understanding

The problem asks us to construct the lexicographically smallest number from a string pattern consisting of 'I' and 'D'. Each character in the pattern defines a relationship between consecutive digits of the number: 'I' indicates that the next digit should be larger than the current, and 'D' indicates the next digit should be smaller. The number is made from digits '1' to '9' with no repetition, and its length is one greater than the length of the pattern.

The input is a string of length n (1 <= n <= 8), which is small enough that we can consider approaches that are not strictly linear. The output is a string of length n+1 representing the smallest number in lexicographic order that satisfies the pattern. Important constraints include ensuring no repeated digits and adhering to the increasing/decreasing requirements at each position.

Edge cases include patterns that are all 'I' (requiring strictly increasing numbers), all 'D' (requiring strictly decreasing numbers), or alternating 'I' and 'D'. Since the maximum length is 8, the largest number involved is at most 9 digits.

Approaches

The brute-force approach would generate all permutations of digits '1' through '9' of length n+1 and check which permutations satisfy the pattern. While correct, this approach is highly inefficient because the number of permutations grows factorially with n (O(9!) worst-case for n = 8). Checking each permutation would require iterating through the pattern to validate, making it slow and unnecessary.

The key insight for a more optimal solution comes from greedy and stack-based construction. Observe that any sequence of consecutive 'D's should be filled with the largest available digits in reverse order. The simplest way to implement this is to iterate over the pattern and whenever we encounter a 'D', we can push the current number onto a stack, continuing until the pattern ends or we see an 'I'. At that point, we pop all elements from the stack to ensure the decreasing sequence is reversed correctly. This method guarantees the lexicographically smallest number because we always place the smallest available digits first.

Approach Time Complexity Space Complexity Notes
Brute Force O(9!) O(n+1) Generate all permutations and check each one against the pattern
Optimal O(n) O(n) Use a stack to handle consecutive decreasing sequences and construct the smallest number greedily

Algorithm Walkthrough

  1. Initialize an empty list result to store the digits of the number and an empty stack stack to manage decreasing sequences.
  2. Iterate over numbers from 1 to n+1, representing candidate digits to place.
  3. Push each digit onto the stack.
  4. If the current position is the end of the pattern or the next character is 'I', pop all elements from the stack and append them to result. This ensures that any preceding 'D' sequence is reversed correctly.
  5. Continue this process until all numbers have been processed.
  6. Join the digits in result into a string and return.

Why it works: The stack ensures that all consecutive decreasing positions are reversed correctly to satisfy the 'D' requirements, while digits are placed in ascending order wherever possible, guaranteeing the lexicographically smallest result.

Python Solution

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        result = []
        stack = []
        n = len(pattern)
        
        for i in range(n + 1):
            stack.append(str(i + 1))
            
            if i == n or pattern[i] == 'I':
                while stack:
                    result.append(stack.pop())
        
        return ''.join(result)

The Python implementation follows the algorithm directly. We iterate from 0 to n (inclusive) and push i+1 onto the stack. Whenever we reach the end or an 'I', we pop all elements from the stack and append them to result. This ensures that all decreasing sequences are reversed correctly while increasing sequences are naturally handled by the order of digits pushed.

Go Solution

func smallestNumber(pattern string) string {
    result := []byte{}
    stack := []byte{}
    n := len(pattern)
    
    for i := 0; i <= n; i++ {
        stack = append(stack, byte('1'+i))
        
        if i == n || pattern[i] == 'I' {
            for len(stack) > 0 {
                result = append(result, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
        }
    }
    
    return string(result)
}

In Go, we use slices of byte for result and stack. Conversion from integer to character is done using byte('1'+i). The pop operation uses slicing, which is idiomatic in Go. The logic mirrors the Python solution closely.

Worked Examples

Example 1: pattern = "IIIDIDDD"

Step i Stack Result
0 1 [1] []
1 2 [2] [1]
2 3 [3] [1,2]
3 4 [4] [1,2,3]
4 5 [5] [1,2,3,4]
5 6 [6] [] (start D sequence)
6 7 [6,7] []
7 8 [6,7,8] []
8 9 [6,7,8,9] [1,2,3,5,4,9,8,7,6]

Final result: "123549876"

Example 2: pattern = "DDD"

Step i Stack Result
0 1 [1] []
1 2 [1,2] []
2 3 [1,2,3] []
3 4 [1,2,3,4] [4,3,2,1]

Final result: "4321"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each digit is pushed and popped from the stack exactly once
Space O(n) Stack and result array each use O(n) space

Since n is at most 8, this algorithm is extremely efficient.

Test Cases

# Provided examples
assert Solution().smallestNumber("IIIDIDDD") == "123549876"  # mixed I and D
assert Solution().smallestNumber("DDD") == "4321"           # all D

# Edge cases
assert Solution().smallestNumber("I") == "12"               # single I
assert Solution().smallestNumber("D") == "21"               # single D
assert Solution().smallestNumber("IID") == "1234"           # ends with D
assert Solution().smallestNumber("DII") == "2143"           # starts with D
assert Solution().smallestNumber("IDID") == "13254"         # alternating pattern
assert Solution().smallestNumber("IIIIIIII") == "123456789" # max length all I
assert Solution().smallestNumber("DDDDDDDD") == "987654321" # max length all D
Test Why
"IIIDIDDD" Mixed I and D pattern to test normal behavior
"DDD" All D pattern to test descending sequences
"I" Single character pattern to test minimum input
"D" Single character pattern descending
"IID" Pattern ending with D
"DII" Pattern starting with D
"IDID" Alternating I and D pattern
"IIIIIIII" Maximum length, all I
"DDDDDDDD" Maximum length, all D

Edge Cases

One important edge case is a pattern of all 'I', which requires strictly increasing numbers. Without careful handling, the algorithm might incorrectly reverse sequences unnecessarily. The stack approach handles this by only popping when an 'I' is encountered, so sequences of 'I' are appended naturally in order.

Another edge case is a pattern of all 'D', which requires strictly decreasing numbers. The algorithm pushes all digits onto the stack first, then pops them at the end to reverse the entire sequence, producing the correct descending number.

A third edge case involves alternating 'I' and 'D'. Naive approaches may fail to properly handle short decreasing sequences. The stack ensures each 'D' sequence is reversed individually, preserving the lexicographically smallest order while satisfying the pattern.

This approach also correctly handles the maximum pattern length of 8, avoiding integer overflow or digit repetition issues.