2434. Using a Robot to Print the Lexicographically Smallest String
Description
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.
Solutions
Solution 1: Greedy + Stack
The problem can be transformed into, given a string sequence, convert it into the lexicographically smallest string sequence with the help of an auxiliary stack.
We can use an array cnt
to maintain the occurrence count of each character in string $s$, use a stack stk
as the auxiliary stack in the problem, and use a variable mi
to maintain the smallest character in the string that has not been traversed yet.
Traverse the string $s$, for each character $c$, we first decrement the occurrence count of character $c$ in array cnt
, and update mi
. Then push character $c$ into the stack. At this point, if the top element of the stack is less than or equal to mi
, then loop to pop the top element of the stack, and add the popped character to the answer.
After the traversal ends, return the answer.
The time complexity is $O(n+C)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$, and $C$ is the size of the character set, in this problem $C=26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|