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 <= 10^5
  • 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

  1. Count the frequency of each character in s.
  2. Iterate through s, pushing each character onto a stack (t).
  3. After each push, update the frequency count.
  4. 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.
  5. Continue until both s and t are empty.

Code

 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)