Problem Statement
You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s andt are both empty:
- Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
- Remove the last character of a string t and give it to the robot. The robot will write this character on paper.
Return the lexicographically smallest string that can be written on the paper.
Example
Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".Approach
While the problem itself seems complicated, the solution is relatively simply using monotonic stacks. While processing the top element of the original stack (string s), if the current character is greater (lexicographically) than the minimum character in the original string, we retain the current character and continue to bring from s until we encounter the smallest character.
Hence, in order to keep track of the smaller character, the usage of hash maps is also required, where we keep track of each alphabet. The time complexity will then be reduced to O(n) from the use of hash maps.
Solution
from collections import defaultdict
class Solution(object):
def robotWithString(self, s):
count = defaultdict(int)
for char in s:
count[char] += 1
st = []
res = []
def min_char(count):
for i in range(26):
ch = chr(ord('a') + i)
if count[ch] > 0:
return ch
for char in s:
count[char] -= 1
st.append(char)
while st and st[-1] <= min_char(count):
res.append(st.pop())
while st:
res.append(st.pop())
return ''.join(res)
Comment
While the problem itself was simple, the explanation made the apporach harder, where I should practice more problems with such confusing wording.
