Leetcode: 2434. Using a Robot to Print the Lexicographically Smallest String

Problem Statement

Understand the problem

Pattern: Find optimal arrangement where you can do two operations: (1) remove first char from the input and add to a stack, (2) remove char from stack and put on the answer. Find the smallest string that can be formed using these rules.

Devise a plan

For each char in the input, add it to the answer if there is no char on the right (rest of the string) that comes first than it. Otherwise, drop all chars from the current stack to the answer while they are smaller than the smaller char to the right. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

Carry out the plan

from sortedcontainers import SortedList


class Solution:
    def robotWithString(self, s: str) -> str:
        rest = SortedList(list(s))
        st = []
        ans = []
        for c in s:
            while st and st[-1] <= rest[0]:
                ans.append(st.pop())
            if c == rest[0]:
                ans.append(c)
                rest.pop(0)
            else:
                st.append(c)
                rest.remove(c)
        while st:
            ans.append(st.pop())
        return "".join(ans)