Construct Smallest Number From DI String

Solution

Greedy

To match the string DDIDDIDD to the sequence 123456789, reverse all numbers between the points labeled as "I" in the sequence. Every time we encounter an I, we reverse everything from the last split up to (and including) the digit at I.

A step-by-step example:

1. Find the first I at position 3
   • Original chunk: 123
   • Reverse it: 321
   • Partial result: 321
2. Second I at position 6
   • Next chunk: 456
   • Reverse it: 654
   • Partial result so far: 321654
3. Reverse the last group (789)
   • Final chunk: 789
   • Reverse it: 987

Putting it all together, we get: 321654987.

def smallestNumber(self, pattern: str) -> str:
    # DDI -> 3214
    res = []
    stack = []
    
    for i, c in enumerate(pattern+'I', 1):
        stack.append(i)
        if c == 'I':
            res.extend(stack[::-1])
            stack = []
    
    return ''.join(map(str, res))