2375. Construct Smallest Number From DI String

Time: O(n)

Space: O(n)

Intuition

Smallest number with pattern where I means increasing, D means decreasing. Greedy: use 1-9 with push/pop stack approach.

Algorithm

1Stack-based: push digits, pop on I to get increasing sequence.
2For i from 0 to n: push i+1. If i==n or pattern[i]==I: pop all stack to result.

Common Pitfalls

•Classic problem: use stack to reverse decreasing runs. Final digit handles trailing Ds.

2375.cs

// Approach: Stack-based construction; push digits and flush on 'I' to produce lexicographically smallest result.
// Time: O(n) Space: O(n)

public class Solution
{
    public string SmallestNumber(string pattern)
    {
        StringBuilder sb = new StringBuilder();
        Stack<char> stack = new Stack<char>();
        stack.Push('1');

        foreach (char c in pattern)
        {
            char maxSoFar = stack.Peek();
            if (c == 'I')
            {
                while (stack.Count > 0)
                {
                    maxSoFar = (char)Math.Max(maxSoFar, stack.Peek());
                    sb.Append(stack.Pop());
                }
            }
            stack.Push((char)(maxSoFar + 1));
        }

        while (stack.Count > 0)
            sb.Append(stack.Pop());

        return sb.ToString();
    }
}

Was this solution helpful?