Leetcode 2375 Construct Smallest Number From DI String - Stack (Med, Java, O(n))

Leetcode 2375: Construct Smallest Number From DI String

🧠 Problem Summary – Leetcode 2375

You are given a string pattern consisting of only the characters 'I' (increase) and 'D' (decrease).

Your task is to construct the lexicographically smallest number that satisfies the pattern using digits from 1 to 9, with no repeated digits.

---

🔢 Example:

Input:

pattern = "IDID"

Output:

"13254"

---

💡 Intuition and Approach

We want the smallest lexicographical number that fits the increasing/decreasing pattern. So we process the pattern left to right using a stack to handle reversals efficiently.

🔄 Key Observation:

• Use a stack to temporarily hold digits.
• Every time you hit an 'I' or reach the end, flush the stack into the result.
• This way, sequences of 'D' cause the digits to appear in decreasing order (due to the stack reversal).

---

🔍 Step-by-Step Example: "IDID"

Pattern length = 4 ⇒ We need digits 1 to 5.

✅ Final result: "13254"

---

⚙️ Java Code

class Solution {
    public String smallestNumber(String pattern) {
        StringBuilder result = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= pattern.length(); i++) {
            stack.push(i + 1); // push next available digit

            if (i == pattern.length() || pattern.charAt(i) == 'I') {
                while (!stack.isEmpty()) {
                    result.append(stack.pop());
                }
            }
        }

        return result.toString();
    }
}

---

⏱️ Time and Space Complexity

Where n = pattern.length().

---

🧠 Why This Works

• 'D' causes us to delay writing digits by stacking them.
• 'I' (or end of input) causes us to flush digits in LIFO order, creating descending sequences.
• By always pushing the smallest available digits (1, 2, 3...), we guarantee the lexicographically smallest result.

---

✅ Key Takeaways

• This is a greedy + stack solution.
• It’s elegant and linear in time and space.
• It works by deferring output until we know the full ascending/descending structure.