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

https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/

initial

So I thought we can jsut detect a downward lexcigoraphical substring and reverse it to our answer string. But this isnt guaranteed like if we have

caba
my way will be acab
but the correct answer is aabc.

So we always have to check for the remaining lowest lexciographical alphabet when we are processing current character. For example "bac", if we are at a and stack ['b'], a is indeed the lowest character but we still need to append a to our stack and not directly to the answer string cuz the 2 options the robot can do do not include directly appending the character to answer string.

Only when we are at c and we see that the top element in stack ('a') is indeed lowest pair, do we then pop that and add that to our answer string.

sol

from collections import Counter
class Solution:
    def robotWithString(self, s: str) -> str:
        ans=""
        dic = Counter(s)
        freq=[]
        def find_lowest_key():
            for i in range(26):
                ch = chr(ord('a')+i)
                if dic[ch]>0:
                    return ch
            return ""

        stack=[]
        for c in s:
            stack.append(c)
            dic[c]-=1
            while stack and stack[-1]<=find_lowest_key():
                ans+=stack.pop()
        if stack:
            ans += ''.join(reversed(stack))
        return ans
        

complexity

n time an space