Problem of The Day: Using a Robot to Print the Lexicographically Smallest String

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def robotWithString(self, s: str) -> str:
        queue = deque(list(s))
        t_queue = deque()
        self.res = []

        def dfs(q, t, curr):
            if len(curr) > len(s):
                return

            if not q and not t:
                curr_str = ''.join(curr)
                res_str = ''.join(self.res)
                if not self.res or (res_str and res_str > curr_str):
                    self.res = curr[:]
                return

            temp_q = deque(list(q))
            temp_t = deque(list(t))

            if temp_q:
                c = temp_q.popleft()
                temp_t.append(c)
                dfs(temp_q, temp_t, curr)

            if t:
                c = t.pop()
                dfs(q, t, curr + [c])


        dfs(queue, t_queue, [])

        return ''.join(self.res)

Editorial

class Solution:
    def robotWithString(self, s: str) -> str:
        cnt = Counter(s)
        stack = []
        res = []
        minCharacter = "a"
        for c in s:
            stack.append(c)
            cnt[c] -= 1
            while minCharacter != "z" and cnt[minCharacter] == 0:
                minCharacter = chr(ord(minCharacter) + 1)
            while stack and stack[-1] <= minCharacter:
                res.append(stack.pop())
        return "".join(res)