You are given a string s
and a robot that currently holds an empty string t
. Apply one of the following 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 character to the stringt
. - 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 1:
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="".
Example 2:
Input: s = "bac" Output: "abc" Explanation: Let p denote the written string. Perform first operation twice p="", s="c", t="ba". Perform second operation twice p="ab", s="c", t="". Perform first operation p="ab", s="", t="c". Perform second operation p="abc", s="", t="".
Example 3:
Input: s = "bdda" Output: "addb" Explanation: Let p denote the written string. Initially p="", s="bdda", t="". Perform first operation four times p="", s="", t="bdda". Perform second operation four times p="addb", s="", t="".
Constraints:
1 <= s.length <= 105
s
consists of only English lowercase letters.
这个题目的主要思路就是判断什么时候可以将t里面的last char 放进p里面,然后t实际上就是一个stack。
判断思路: 将s 利用collections.Counter() 来将每个char的frequency得到,然后得到最小的char low。只要t[-1] <= low, 即可以把t.pop()
T: O(n) S: O(n)
class Solution: def robotWithString(self, s: str) -> str: count = collections.Counter(s) t, p = [], "" low = 'a' for c in s: t.append(c) count[c] -= 1 while low < 'z' and count[low] == 0: low = chr(ord(low) + 1) while t and t[-1] <= low: p += t.pop() return p
- Lexicographically String_Medium LeetCode Smallest Mediumlexicographically string_medium leetcode smallest lexicographically palindrome leetcode smallest lexicographically elements smallest swapping string_medium leetcode infinite smallest number grid_medium leetcode number medium lexicographically smallest srop-smallest largest-smallest-cyclic-shift