LeetCode 2434. Using a Robot to Print the Lexicographically Smallest String Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Greedy + Stack

The problem can be transformed into: given a string sequence, use an auxiliary stack to convert it into the lexicographically smallest string sequence.

We can use an array cnt to maintain the count of each character in string s, use a stack stk as the auxiliary stack mentioned in the problem, and use a variable mi to keep track of the smallest character not yet traversed in the string.

Traverse the string s. For each character c, first decrement its count in the array cnt and update mi. Then push c onto the stack. At this point, if the top element of the stack is less than or equal to mi, repeatedly pop the top element from the stack and add it to the answer.

After the traversal, return the answer.

The time complexity is O(n + |Σ|), and the space complexity is O(n), where n is the length of the string s and |Σ| is the size of the character set, which is 26 in this problem.

PythonJavaC++GoTypeScriptRust

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)(code-box)

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(); } }(code-box)

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; } };(code-box)

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) }(code-box)

function robotWithString(s: string): string { const cnt = new Map<string, number>(); for (const c of s) { cnt.set(c, (cnt.get(c) || 0) + 1); } const ans: string[] = []; const stk: string[] = []; let mi = 'a'; for (const c of s) { cnt.set(c, (cnt.get(c) || 0) - 1); while (mi < 'z' && (cnt.get(mi) || 0) === 0) { mi = String.fromCharCode(mi.charCodeAt(0) + 1); } stk.push(c); while (stk.length > 0 && stk[stk.length - 1] <= mi) { ans.push(stk.pop()!); } } return ans.join(''); }(code-box)

impl Solution { pub fn robot_with_string(s: String) -> String { let mut cnt = [0; 26]; for &c in s.as_bytes() { cnt[(c - b'a') as usize] += 1; } let mut ans = Vec::with_capacity(s.len()); let mut stk = Vec::new(); let mut mi = 0; for &c in s.as_bytes() { cnt[(c - b'a') as usize] -= 1; while mi < 26 && cnt[mi] == 0 { mi += 1; } stk.push(c); while let Some(&top) = stk.last() { if (top - b'a') as usize <= mi { ans.push(stk.pop().unwrap()); } else { break; } } } String::from_utf8(ans).unwrap() } }(code-box)