Problem#
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 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.
Examples#
Example 1:
1
2
3
4
5
6
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:
1
2
3
4
5
6
7
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:
1
2
3
4
5
6
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.
Solution#
Method 1 – Greedy Stack Simulation#
Intuition#
The key idea is to always write the smallest possible character to the paper at each step. We use a stack to simulate the robot’s string t
. By tracking the smallest character remaining in s
, we can decide whether to pop from t
or push from s
to ensure lexicographical order.
Approach#
Count the frequency of each character in s
.
Iterate through s
, pushing each character onto a stack (t
).
After each push, update the frequency count.
While the top of the stack is less than or equal to the smallest character left in s
, pop from the stack and append to the answer.
Continue until both s
and t
are empty.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
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
class Solution {
public :
string robotWithString(string s) {
vector< int > cnt(26 , 0 );
for (char c : s) cnt[c - 'a' ]++ ;
string ans;
vector< char > stk;
int n = s.size(), i = 0 ;
for (char c : s) {
stk.push_back(c);
cnt[c - 'a' ]-- ;
while (! stk.empty()) {
bool canPop = true;
for (int j = 0 ; j < stk.back() - 'a' ; ++ j) {
if (cnt[j] > 0 ) {
canPop = false;
break ;
}
}
if (canPop) {
ans += stk.back();
stk.pop_back();
} else break ;
}
}
while (! stk.empty()) {
ans += stk.back();
stk.pop_back();
}
return ans;
}
};
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
type Solution struct {}
func (Solution ) RobotWithString (s string ) string {
cnt := [26 ]int {}
for _ , c := range s {
cnt [c - 'a' ]++
}
ans := []byte {}
stk := []byte {}
for i := 0 ; i < len(s ); i ++ {
stk = append(stk , s [i ])
cnt [s [i ]- 'a' ]--
for len(stk ) > 0 {
canPop := true
for j := 0 ; j < int(stk [len(stk )- 1 ]- 'a' ); j ++ {
if cnt [j ] > 0 {
canPop = false
break
}
}
if canPop {
ans = append(ans , stk [len(stk )- 1 ])
stk = stk [:len(stk )- 1 ]
} else {
break
}
}
}
for len(stk ) > 0 {
ans = append(ans , stk [len(stk )- 1 ])
stk = stk [:len(stk )- 1 ]
}
return string(ans )
}
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
class Solution {
public String robotWithString (String s) {
int [] cnt = new int [ 26] ;
for (char c : s.toCharArray ()) cnt[ c - 'a' ]++ ;
StringBuilder ans = new StringBuilder();
Deque< Character> stk = new ArrayDeque<> ();
for (char c : s.toCharArray ()) {
stk.push (c);
cnt[ c - 'a' ]-- ;
while (! stk.isEmpty ()) {
boolean canPop = true ;
for (int j = 0; j < stk.peek () - 'a' ; ++ j) {
if (cnt[ j] > 0) {
canPop = false ;
break ;
}
}
if (canPop) ans.append (stk.pop ());
else break ;
}
}
while (! stk.isEmpty ()) ans.append (stk.pop ());
return ans.toString ();
}
}
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
class Solution {
fun robotWithString (s: String): String {
val cnt = IntArray(26 )
for (c in s) cnt[c - 'a' ]++
val ans = StringBuilder()
val stk = ArrayDeque<Char>()
for (c in s) {
stk.addLast(c)
cnt[c - 'a' ]--
while (stk.isNotEmpty()) {
var canPop = true
for (j in 0 until (stk.last() - 'a' )) {
if (cnt[j] > 0 ) {
canPop = false
break
}
}
if (canPop) ans.append(stk.removeLast())
else break
}
}
while (stk.isNotEmpty()) ans.append(stk.removeLast())
return ans.toString()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution :
def robotWithString (self, s: str) -> str:
from collections import Counter
cnt: dict[str, int] = Counter(s)
stk: list[str] = []
ans: list[str] = []
for c in s:
stk. append(c)
cnt[c] -= 1
while stk:
top = stk[- 1 ]
if all(cnt[chr(j + ord('a' ))] == 0 for j in range(ord(top) - ord('a' ))):
ans. append(stk. pop())
else :
break
while stk:
ans. append(stk. pop())
return '' . join(ans)
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
impl Solution {
pub fn robot_with_string (s: String) -> String {
let mut cnt = [0 ; 26 ];
for & b in s.as_bytes() {
cnt[(b - b 'a' ) as usize ] += 1 ;
}
let mut stk = Vec::new();
let mut ans = Vec::new();
for & b in s.as_bytes() {
stk.push(b);
cnt[(b - b 'a' ) as usize ] -= 1 ;
while let Some(& top) = stk.last() {
let mut can_pop = true ;
for j in 0 .. (top - b 'a' ) as usize {
if cnt[j] > 0 {
can_pop = false ;
break ;
}
}
if can_pop {
ans.push(stk.pop().unwrap());
} else {
break ;
}
}
}
while let Some(x) = stk.pop() {
ans.push(x);
}
String::from_utf8(ans).unwrap()
}
}
Complexity#
⏰ Time complexity: O(n * 26)
(where n
is the length of s
; for each character, we may check up to 26 letters)
🧺 Space complexity: O(n)
(for the stack and answer)