Problem Informations

• Problem Index: 2375
• Problem Link: Construct Smallest Number From DI String
• Topics: String, Backtracking, Stack, Greedy

Problem Description

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:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then $num[i] < num[i + 1]$.
• If pattern[i] == 'D', then $num[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 \leq \text{pattern.length} \leq 8$
• pattern consists of only the letters 'I' and 'D'.

Intuition

The problem revolves around constructing a string of digits that matches a given pattern of increasing and decreasing relationships. The need to generate the lexicographically smallest string suggests maintaining an orderly sequence, where the increasing subsequence condition (‘I’) is naturally satisfied by using the smallest unused numbers sequentially. Contrarily, for the decreasing subsequence condition (‘D’), the larger numbers are to precede the smaller ones. To keep track of ordering effectively while ensuring optimal minimal lexicographic order, utilizing a stack data structure can be beneficial. This approach capitalizes on the ‘Last-In, First-Out’ property of stacks, enabling us to reverse subsequences on demand.

Approach

The method involves iterating through each character in the given pattern. We must generate a sequence of numbers that abides by the pattern rules:

1. Initialize Structures: Create an empty string result for storing the final number and a stack st to manage digit ordering.

2. Iterate Over the Pattern:

   • For each index i up to the length of the pattern (inclusive of an additional step to handle the last character due to n + 1 length of result), push the next available number (i + 1) onto the stack.
   • Check two scenarios:
     • When we reach the end of the pattern.
     • When the current character pattern[i] is ‘I’.

3. Constructing the Result:

   • While the stack is not empty and either of the above conditions are met, pop the top element from the stack and append it to result. This operation is performed to enforce the smallest possible lexicographical order whenever an ‘I’ is encountered or we have processed all characters in pattern.

4. Completion:

   • Return the result, which should now contain the smallest possible number satisfying the given pattern constraints.

This approach effectively leverages the stack to ensure decreasing segments are resolved in reverse order, thus naturally accounting for the pattern’s requirements while maintaining lexicographical priority.

Code

C++

class Solution {
public:
    string smallestNumber(string pattern) {
        string result = "";  // Variable to store the final result
        stack<int> st;       // Stack to help with generating the number

        // Iterate through the pattern, and handle one more digit than the pattern's length
        for(int i = 0; i <= pattern.size(); i++) {
            // Push the next increasing digit onto the stack
            st.push(i + 1);

            // If we reach the end of the pattern or encounter an 'I', construct the lexicographically smallest number
            while(!st.empty() && (i == pattern.size() || pattern[i] == 'I')) {
                // Pop from stack and append to result to ensure the sequence conditions
                result += '0' + st.top();
                st.pop();
            }
        }

        return result;  // Return the smallest number that matches the pattern
    }
};

Python

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        result = ""  # Variable to store the final result
        st = []  # Stack to help with generating the number

        # Iterate through the pattern, and handle one more digit than the pattern's length
        for i in range(len(pattern) + 1):
            # Push the next increasing digit onto the stack
            st.append(i + 1)

            # If we reach the end of the pattern or encounter an 'I', construct the lexicographically smallest number
            while st and (i == len(pattern) or pattern[i] == 'I'):
                # Pop from stack and append to result to ensure the sequence conditions
                result += str(st.pop())
        
        return result  # Return the smallest number that matches the pattern

Complexity

• Time complexity: $O(n)$
  The algorithm iterates through each character of the pattern, which is of length $n$. For each character, the algorithm may push a single element onto the stack. Then, under certain conditions (end of the pattern or encountering an ‘I’), it will pop all elements from the stack, each of which can occur at most once per character of the pattern. Therefore, each element is processed (pushed and popped) once, leading to a linear time complexity relative to the length of the pattern, which is $O(n)$.

• Space complexity: $O(n)$
  The space complexity is determined by the auxiliary stack used in the algorithm. In the worst-case scenario, where the entire pattern consists of ‘D’s, all possible numbers (of up to size $n+1$) are pushed onto the stack before any is popped. Thus, the stack can contain at most $n+1$ elements, resulting in a space complexity of $O(n)$.