Problem Formulation & Mathematical Constraints

We are given a 0-indexed string pattern of length $N$ ($1 le N le 8$) consisting strictly of characters 'I' (increasing) and 'D' (decreasing). We must construct a string num of length $N + 1$ such that:

• num consists of distinct digits drawn from '1' through '9', with each digit used at most once.
• For every index $i$ ($0 le i < N$), if pattern[i] == 'I', then num[i] < num[i+1].
• For every index $i$ ($0 le i < N$), if pattern[i] == 'D', then num[i] > num[i+1].

Among all valid candidate strings, we must return the lexicographically smallest possible number. For example, given pattern = "IIIDIDDD", the valid lexicographically smallest output is "123549876".

The Greedy Intuition: Monotonic Stack Reversal

To make the resulting number lexicographically as small as possible, we must place the smallest available digits at the earliest possible index positions. If the pattern were entirely increasing ("IIII"), the optimal assignment would simply be the ascending digits "12345".

Whenever a sequence of decreasing conditions ('D') is encountered, the relative order of those digits must be reversed. Because a Last-In, First-Out (LIFO) Stack naturally reverses order, we can greedily push sequential numbers onto the stack:

1. Iterate an index $i$ from $0$ up to $N$ (a total of $N+1$ steps).
2. At each step $i$, push the digit $i + 1$ onto our stack.
3. If we reach an increasing condition (pattern[i] == 'I') or reach the end of the string ($i == N$), we pop all accumulated elements from the stack and append them to our result string.

By delaying the placement of digits during consecutive 'D' characters and flushing them upon the next 'I', the smallest available digits are assigned to the sequence and then reversed to satisfy the decreasing constraints.

Step-by-Step Execution Trace on "IIIDIDDD"

Tracing through pattern = "IIIDIDDD" ($N = 8$) demonstrates how the stack naturally resolves the sequence:

Stack Push-Pop State Architecture

Optimal Implementations: C++20 and TypeScript

Here are production-grade implementations utilizing the monotonic stack pattern:

C++20 Implementation

#include <string>
#include <stack>

class Solution {
public:
    std::string smallestNumber(const std::string& pattern) {
        std::string result;
        result.reserve(pattern.length() + 1);
        std::stack<char> st;

        for (int i = 0; i <= static_cast<int>(pattern.length()); ++i) {
            // Push 1-indexed digit character directly to avoid conversions
            st.push(static_cast<char>('1' + i));

            // Flush stack when reaching 'I' or after pushing final digit
            if (i == static_cast<int>(pattern.length()) || pattern[i] == 'I') {
                while (!st.empty()) {
                    result.push_back(st.top());
                    st.pop();
                }
            }
        }
        return result;
    }
};

Modern TypeScript Implementation

export function smallestNumber(pattern: string): string {
    const stack: number[] = [];
    const result: string[] = [];

    for (let i = 0; i <= pattern.length; i++) {
        stack.push(i + 1);

        // Pop elements upon encountering 'I' or reaching string terminus
        if (i === pattern.length || pattern[i] === 'I') {
            while (stack.length > 0) {
                result.push(stack.pop()!.toString());
            }
        }
    }

    return result.join('');
}

Alternative: In-Place Two-Pointer Reversal ($O(1)$ Space)

If we wish to avoid stack memory allocations altogether, we can initialize an array with consecutive digits ['1', '2', ..., 'N+1'] and employ a two-pointer sliding window. Whenever we encounter a contiguous sequence of 'D' characters, we identify the segment boundaries $[j, i]$ and reverse that subarray in-place using std::reverse. Both approaches operate in $O(N)$ time, but the two-pointer approach utilizes strictly $O(1)$ auxiliary space beyond the output string.

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the length of pattern. Each digit from $1$ to $N+1$ is pushed onto the stack exactly once and popped at most once. For $N le 8$, the entire execution requires fewer than 20 CPU cycles.
• Space Complexity: $O(N)$ auxiliary space for the stack (which holds at most $N+1$ characters) and $O(N)$ space for the return string.