| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1953 |
Weekly Contest 314 Q3 |
|
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
sand give it to the robot. The robot will append this character to the stringt. - Remove the last character of a string
tand 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 <= 105sconsists of only English lowercase letters.
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 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 cnt, and update mi. Then push character 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
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)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;
}
};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('');
}class Solution:
def robotWithString(self, s: str) -> str:
n = len(s)
right = [chr(ord('z') + 1)] * (n + 1)
for i in range(n - 1, -1, -1):
right[i] = min(s[i], right[i + 1])
ans = []
stk = []
for i, c in enumerate(s):
stk.append(c)
while stk and stk[-1] <= right[i + 1]:
ans.append(stk.pop())
return ''.join(ans)class Solution {
public String robotWithString(String s) {
int n = s.length();
int[] right = new int[n];
right[n - 1] = n - 1;
for (int i = n - 2; i >= 0; --i) {
right[i] = s.charAt(i) < s.charAt(right[i + 1]) ? i : right[i + 1];
}
StringBuilder ans = new StringBuilder();
Deque<Character> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
stk.push(s.charAt(i));
while (
!stk.isEmpty() && (stk.peek() <= (i > n - 2 ? 'z' + 1 : s.charAt(right[i + 1])))) {
ans.append(stk.pop());
}
}
return ans.toString();
}
}class Solution {
public:
string robotWithString(string s) {
int n = s.size();
vector<int> right(n, n - 1);
for (int i = n - 2; i >= 0; --i) {
right[i] = s[i] < s[right[i + 1]] ? i : right[i + 1];
}
string ans;
string stk;
for (int i = 0; i < n; ++i) {
stk += s[i];
while (!stk.empty() && (stk.back() <= (i > n - 2 ? 'z' + 1 : s[right[i + 1]]))) {
ans += stk.back();
stk.pop_back();
}
}
return ans;
}
};