Using a Robot to Print the Lexicographically Smallest String Solution
Using a Robot to Print the Lexicographically Smallest String solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Using a Robot to Print the Lexicographically Smallest String is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Greedy, Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A robot holds a string t that starts empty, and you are given a string s. Until both s and t are empty, repeatedly perform one of these operations:
- Remove the first character of
sand append it to the end oft. - Remove the last character of
tand write it on paper.
(t behaves like a stack.) Return the lexicographically smallest string that can end up written on the paper.
Example 1
Input: s = "kairo"
Output: aikor
Explanation: Push `k` and `a`, write `a`; push `i`, write `i` and `k`; push `r` and `o`, write `o` and `r`.
Example 2
Input: s = "zza"
Output: azz
Explanation: Push everything, then write `a`, `z`, `z`.
Example 3
Input: s = "cbca"
Output: acbc
Constraints
1 <= s.length <= 10^5s consists of only lowercase English letters
Hints for Using a Robot to Print the Lexicographically Smallest String
Hint 1
The paper should receive the smallest letter available as early as possible.
Hint 2
Writing the top of
tis a good idea when nothing still waiting insis smaller than it — otherwise you would rather fetch that smaller letter first.Hint 3
Keep counts of the letters remaining in
sand the smallest of them. After each push, pop while the top oftis at most that smallest remaining letter.
How to solve Using a Robot to Print the Lexicographically Smallest String
Greedy with a stack: after pushing each character, write the top of the stack while it is no larger than the smallest letter still unread in s.
Approach
- Count the letters of
s;lowis the smallest letter with a non-zero count. - For each character of
s: push it, decrease its count, and advancelowpast letters whose count dropped to zero. - While the stack is non-empty and its top is
<= low, pop it onto the answer. (Oncesis exhausted,lowmoves pastzand everything is popped.)
Why it works
At any moment the next letter written is either the stack's top or some letter still in s (which can only be written after pushing everything in front of it). If the top is no larger than every remaining letter of s, writing it now cannot hurt: any smaller-or-equal letter we might reach later is no better, and delaying it only buries it. If some remaining letter is strictly smaller than the top, writing the top now would put a larger letter where a smaller one could go, so we must keep reading. Ties favour writing, since an equal letter later gains nothing and the written prefix is the same.
Complexity
- Time —
O(n + 26) - Space —
O(n) for the stack
Pitfalls
- Compare with the smallest letter still in
s(strictly after the current position), not including letters already pushed. - Pop on equality (
<=), otherwise"zza"-style inputs keep equal letters buried behind larger ones. - Recomputing the suffix minimum by scanning is O(n²); keep counts or a suffix-minimum array.
Reference solution
Python
def robotWithString(s: str) -> str:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - 97] += 1
low = 0
stack = []
out = []
for ch in s:
c = ord(ch) - 97
stack.append(c)
cnt[c] -= 1
while low < 26 and cnt[low] == 0:
low += 1
while stack and stack[-1] <= low:
out.append(chr(stack.pop() + 97))
return "".join(out)Java
public static String robotWithString(String s) {
int n = s.length();
int[] cnt = new int[26];
for (int i = 0; i < n; i++) cnt[s.charAt(i) - 'a']++;
char[] st = new char[n];
int top = 0, low = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
st[top++] = ch;
cnt[ch - 'a']--;
while (low < 26 && cnt[low] == 0) low++;
while (top > 0 && st[top - 1] - 'a' <= low) sb.append(st[--top]);
}
return sb.toString();
}C++
string robotWithString(string s) {
int cnt[26] = {0};
for (char ch : s) cnt[ch - 'a']++;
string st, out;
int low = 0;
for (char ch : s) {
st.push_back(ch);
cnt[ch - 'a']--;
while (low < 26 && cnt[low] == 0) low++;
while (!st.empty() && st.back() - 'a' <= low) {
out.push_back(st.back());
st.pop_back();
}
}
return out;
}JavaScript
var robotWithString = function(s) {
var cnt = new Array(26).fill(0);
for (var i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
var low = 0, stack = [], out = [];
for (var j = 0; j < s.length; j++) {
var c = s.charCodeAt(j) - 97;
stack.push(c);
cnt[c]--;
while (low < 26 && cnt[low] === 0) low++;
while (stack.length && stack[stack.length - 1] <= low) out.push(String.fromCharCode(97 + stack.pop()));
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets