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 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 <= 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).