##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2434.html

# 2434. Using a Robot to Print the Lexicographically Smallest String

• Difficulty: Medium.
• Related Topics: Hash Table, String, Stack, Greedy.
• Similar Questions: Find Permutation.

## 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.

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"
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 (Java, C++, Python)

• 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<>();
char mi = 'a';
for (char c : s.toCharArray()) {
--cnt[c - 'a'];
while (mi < 'z' && cnt[mi - 'a'] == 0) {
++mi;
}
stk.push(c);
while (!stk.isEmpty() && stk.peek() <= mi) {
ans.append(stk.pop());
}
}
return ans.toString();
}
}

• class Solution {
public:
string robotWithString(string s) {
int cnt[26] = {0};
for (char& c : s) ++cnt[c - 'a'];
char mi = 'a';
string stk;
string ans;
for (char& c : s) {
--cnt[c - 'a'];
while (mi < 'z' && cnt[mi - 'a'] == 0) ++mi;
stk += c;
while (!stk.empty() && stk.back() <= mi) {
ans += stk.back();
stk.pop_back();
}
}
return ans;
}
};

• class Solution:
def robotWithString(self, s: str) -> str:
cnt = Counter(s)
ans = []
stk = []
mi = 'a'
for c in s:
cnt[c] -= 1
while mi < 'z' and cnt[mi] == 0:
mi = chr(ord(mi) + 1)
stk.append(c)
while stk and stk[-1] <= mi:
ans.append(stk.pop())
return ''.join(ans)


• func robotWithString(s string) string {
cnt := make([]int, 26)
for _, c := range s {
cnt[c-'a']++
}
mi := byte('a')
stk := []byte{}
ans := []byte{}
for i := range s {
cnt[s[i]-'a']--
for mi < 'z' && cnt[mi-'a'] == 0 {
mi++
}
stk = append(stk, s[i])
for len(stk) > 0 && stk[len(stk)-1] <= mi {
ans = append(ans, stk[len(stk)-1])
stk = stk[:len(stk)-1]
}
}
return string(ans)
}

• function robotWithString(s: string): string {
let cnt = new Array(128).fill(0);
for (let c of s) cnt[c.charCodeAt(0)] += 1;
let min_index = 'a'.charCodeAt(0);
let ans = [];
let stack = [];
for (let c of s) {
cnt[c.charCodeAt(0)] -= 1;
while (min_index <= 'z'.charCodeAt(0) && cnt[min_index] == 0) {
min_index += 1;
}
stack.push(c);
while (
stack.length > 0 &&
stack[stack.length - 1].charCodeAt(0) <= min_index
) {
ans.push(stack.pop());
}
}
return ans.join('');
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).