Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The robot's temporary string is a stack. Printing its top is safe when that character is no larger than any unread character; waiting cannot produce a smaller next character. Otherwise, read more input to expose a better choice first.

Approach

Count unread character frequencies. For each input character, push it onto the stack and decrement its remaining count. Advance a pointer to the smallest still-unread letter, then pop and output stack characters while they are at most that letter. The pointer moves only forward because unread counts only decrease. After all input is consumed, Python leaves the pointer at z and JavaScript advances just past z; either value allows every remaining lowercase stack character to be printed. Join the output characters to obtain the smallest possible result.

class Solution:
    def robotWithString(self, s: str) -> str:
        map = defaultdict(int)
        for x in s: map[x] += 1

        min_char = 'a'
        t = [] # stack
        p = [] # result

        for c in s:
            t.append(c)
            map[c] -= 1
            while min_char != 'z' and map[min_char] == 0:
                min_char = chr(ord(min_char) + 1)
            while t and t[-1] <= min_char:
                p.append(t.pop())
        
        return "".join(p)

Complexity analysis

Let n = s.length and A = 26. Each character is pushed and popped at most once while the minimum remaining character advances monotonically. Both solutions therefore take O(n + A) time and O(n + A) auxiliary space for frequencies, the stack, and output.