Using a Robot to Print the Lexicographically Smallest String

main.md

Question

Approach

To get the lexicographically smallest string that can be written on paper, I simulate the robot's operations using a monotonic greedy approach. As I traverse the input string s, I push each character into a stack t (representing the robot's hand). Before moving to the next character, I decide whether to pop from the stack and write to the result based on whether the top of the stack is less than or equal to the smallest character remaining in s. To do this efficiently, I precompute an array min_char where min_char[i] stores the smallest character from s[i] to the end. At each step, if the top of the stack is smaller than or equal to the future minimum, I pop it and add it to the result.

Implementation

class Solution:
    def robotWithString(self, s: str) -> str:
        t = []
        result = []
        n = len(s)

        min_char = [None] * n
        min_char[-1] = s[-1]
        for i in range(n - 2, -1, -1):
            min_char[i] = min(s[i], min_char[i + 1])

        for i in range(n):
            t.append(s[i])
            while t and (i == n - 1 or t[-1] <= min_char[i + 1]):
                result.append(t.pop())

        return ''.join(result)

Complexities

• Time: O(n)
• Space: O(n)