aboutsummaryrefslogtreecommitdiff
path: root/using_robot_print_lex_small_str.py
blob: 318946424bc6ca45349dd88018c8006f78ac9d97 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 2434. Using a Robot to Print the Lexicographically Smallest String
from collections import Counter

"""
you are given a string 's' and a robot that currently holds an empty string
't'. apply one of the followiing operations until 's' and 't' are both empty.
remove the first character of a string 's' and give it to the robot. the
robot will append this charcter 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.
"""


class Solution(object):
    def robotWithString(self, s):
        """
        :type s: str
        :rtype: str
        """
        cnt, low, ans, t = Counter(s), "a", [], []
        for i in s:
            t += i
            cnt[i] -= 1
            while low < "z" and cnt[low] == 0:
                low = chr(ord(low) + 1)
            while t and t[-1] <= low:
                ans += t.pop()
        return "".join(ans)


if __name__ == "__main__":
    obj = Solution()
    print(obj.robotWithString(s="zza"))
    print(obj.robotWithString(s="bac"))
    print(obj.robotWithString(s="bdda"))