Robert BaindourovNodeJS, ReactJS, ElectronJS - Web Software Architect

Featured Summary: The "Construct the Smallest Number" problem requires building the lexicographically smallest sequence of digits from 1 to 9 based on an input string of 'I' (increasing) and 'D' (decreasing) characters. An optimal solution uses a stack data structure in C++ to reverse digit sequences during 'D' patterns, ensuring O(N) time complexity and fulfilling all conditions without reusing digits.

Introduction to String Pattern Algorithms

Developers frequently test their algorithmic expertise through platforms like LeetCode, HackerRank, and GeeksforGeeks. While creating a green GitHub commit history or contributing to open source projects builds real-world engineering skills, mastering logical puzzles remains a core component of technical interviews. The "Construct the Smallest Number" string pattern challenge is an excellent test of utilizing fundamental data structures—specifically the stack—to parse and interpret structured sequences efficiently. Whether you are grinding LeetCode or preparing for a system design interview, understanding these lexicographically smallest permutations is vital.

Problem Statement and Requirements

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 Scenarios and Edge Cases

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 <= pattern.length <= 8
• pattern consists of only the letters 'I' and 'D'.

Optimized C++ Stack-Based Solution

To achieve the lexicographically smallest string, we can iterate from 1 to n+1. We push the current number to a stack. If we reach the end of the string or encounter an 'I' (increasing pattern), we pop all elements from the stack and append them to our result. This elegantly reverses the numbers associated with 'D' (decreasing) sequences while maintaining the smallest possible leading digits.

class Solution {
public:
    string smallestNumber(string pattern) {
        string result;
        stack<int> st;
        for( int i = 0; i <= pattern.size(); i++ ) {
            st.push(i + 1);
            if ( i == pattern.length() || pattern[i] == 'I' ) {
                while(!st.empty()) {
                    result += to_string( st.top() );
                    st.pop();        
                }
            }
        }
        return result;
    }
};
  

Frequently Asked Questions (FAQ)