Using a Robot to Print the Lexicographically Smallest String
Using a Robot to Print the Lexicographically Smallest String is a medium monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (stack + suffix minimum), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every order of moves) up.
Problem
A robot holds a string s and an initially empty string t. Until both are empty, it repeatedly does one of two moves:
- take the first character of
sand append it to the end oft, or - take the last character of
tand write it on paper.
Return the lexicographically smallest string the robot can end up writing.
Examples
Example 1
- Input
s = "cab"- Output
"abc"- Why
- Move 'c' and 'a' onto t, write 'a', move 'b' onto t, then write 'b' and 'c' from the end of t.
Example 2
- Input
s = "dcba"- Output
"abcd"- Why
- Moving every letter onto t first and then writing them back from the end reverses the string.
Example 3
- Input
s = "bxbz"- Output
"bbxz"- Why
- Write the first 'b' at once, keep 'x' waiting in t, write the second 'b', then 'x' and finally 'z'.
Constraints
1 <= s.length <= 10^5scontains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every order of moves) | Exponential | O(n²) |
| Optimal (stack + suffix minimum) | O(n) | O(n) |
1Brute force (try every order of moves)
ExponentialThe number of move orders grows like the Catalan numbers.O(n²)Recursion depth 2n, each frame holding strings of length up to n.At every moment the robot can either move the next letter of s onto t or write the last letter of t. Explore both choices recursively and return the smallest complete output. Every complete output has length n, so plain string comparison picks the best one.
- best(i, t): if i == n and t is empty, return "".
- Option 1 (if i < n): best(i + 1, t + s[i]).
- Option 2 (if t is not empty): last letter of t + best(i, t without its last letter).
- Return the smaller option; the answer is best(0, "").
class Solution {
public String robotWithString(String s) {
return best(s, 0, "");
}
private String best(String s, int i, String t) {
if (i == s.length() && t.isEmpty()) return "";
String res = null;
if (i < s.length()) res = best(s, i + 1, t + s.charAt(i));
if (!t.isEmpty()) {
String cand = t.charAt(t.length() - 1) + best(s, i, t.substring(0, t.length() - 1));
if (res == null || cand.compareTo(res) < 0) res = cand;
}
return res;
}
}class Solution:
def robotWithString(self, s: str) -> str:
n = len(s)
def best(i: int, t: str) -> str:
if i == n and not t:
return ""
res = None
if i < n:
res = best(i + 1, t + s[i])
if t:
cand = t[-1] + best(i, t[:-1])
if res is None or cand < res:
res = cand
return res
return best(0, "")class Solution {
string best(const string& s, int i, const string& t) {
if (i == (int)s.size() && t.empty()) return "";
bool has = false;
string res;
if (i < (int)s.size()) {
res = best(s, i + 1, t + s[i]);
has = true;
}
if (!t.empty()) {
string cand = string(1, t.back()) + best(s, i, t.substr(0, t.size() - 1));
if (!has || cand < res) res = cand;
}
return res;
}
public:
string robotWithString(string s) {
return best(s, 0, "");
}
};function robotWithString(s) {
const n = s.length;
const best = (i, t) => {
if (i === n && t.length === 0) return "";
let res = null;
if (i < n) res = best(i + 1, t + s[i]);
if (t.length > 0) {
const cand = t[t.length - 1] + best(i, t.slice(0, -1));
if (res === null || cand < res) res = cand;
}
return res;
};
return best(0, "");
}2Optimal (stack + suffix minimum)
O(n)Each letter is pushed once and popped once.O(n)The suffix-minimum array, the stack and the output.Treat t as a stack. Precompute minRight[i], the smallest letter in s[i..]. After pushing s[i], keep writing the top of the stack while it is no larger than minRight[i + 1]: nothing still coming can beat it, and waiting would only let larger letters get in front. Once s is used up, write out the rest of the stack.
- minRight[n] = a sentinel larger than 'z'; minRight[i] = min(s[i], minRight[i + 1]).
- For each i: push s[i]; while the stack is not empty and top <= minRight[i + 1], pop and append to the answer.
- Pop everything left and append it.
class Solution {
public String robotWithString(String s) {
int n = s.length();
char[] minRight = new char[n + 1];
minRight[n] = (char) ('z' + 1);
for (int i = n - 1; i >= 0; i--) {
minRight[i] = (char) Math.min(s.charAt(i), minRight[i + 1]);
}
StringBuilder out = new StringBuilder();
char[] st = new char[n];
int top = 0;
for (int i = 0; i < n; i++) {
st[top++] = s.charAt(i);
while (top > 0 && st[top - 1] <= minRight[i + 1]) {
out.append(st[--top]);
}
}
while (top > 0) out.append(st[--top]);
return out.toString();
}
}class Solution:
def robotWithString(self, s: str) -> str:
n = len(s)
min_right = ["{"] * (n + 1) # '{' comes right after 'z'
for i in range(n - 1, -1, -1):
min_right[i] = min(s[i], min_right[i + 1])
out = []
st = []
for i in range(n):
st.append(s[i])
while st and st[-1] <= min_right[i + 1]:
out.append(st.pop())
while st:
out.append(st.pop())
return "".join(out)class Solution {
public:
string robotWithString(string s) {
int n = s.size();
vector<char> minRight(n + 1, 'z' + 1);
for (int i = n - 1; i >= 0; i--) {
minRight[i] = min(s[i], minRight[i + 1]);
}
string out, st;
for (int i = 0; i < n; i++) {
st.push_back(s[i]);
while (!st.empty() && st.back() <= minRight[i + 1]) {
out.push_back(st.back());
st.pop_back();
}
}
while (!st.empty()) {
out.push_back(st.back());
st.pop_back();
}
return out;
}
};function robotWithString(s) {
const n = s.length;
const minRight = new Array(n + 1).fill("{"); // '{' comes right after 'z'
for (let i = n - 1; i >= 0; i--) {
minRight[i] = s[i] < minRight[i + 1] ? s[i] : minRight[i + 1];
}
const out = [];
const st = [];
for (let i = 0; i < n; i++) {
st.push(s[i]);
while (st.length > 0 && st[st.length - 1] <= minRight[i + 1]) {
out.push(st.pop());
}
}
while (st.length > 0) out.push(st.pop());
return out.join("");
}Edge cases to test
- A single character
- Already sorted input, where every letter can be written right away
- Reverse-sorted input, where everything waits in t until the end
- Repeated smallest letters, where a waiting letter equal to the smallest remaining one should be written immediately
Hints
Hint 1
t behaves like a stack: letters go on top and are written from the top.
Hint 2
Writing the top of t now is a good idea exactly when no smaller letter is still left in s.
Hint 3
Precompute, for every position, the smallest letter in the rest of s.
FAQ
What is the best time complexity for Using a Robot to Print the Lexicographically Smallest String?
Optimal (stack + suffix minimum) runs in O(n) time and O(n) extra space. Each letter is pushed once and popped once.
Which pattern does Using a Robot to Print the Lexicographically Smallest String use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Using a Robot to Print the Lexicographically Smallest String?
Yes. Brute force (try every order of moves) takes Exponential time and O(n²) space. At every moment the robot can either move the next letter of s onto t or write the last letter of t.
Which edge cases should I test for Using a Robot to Print the Lexicographically Smallest String?
A single character; Already sorted input, where every letter can be written right away; Reverse-sorted input, where everything waits in t until the end; Repeated smallest letters, where a waiting letter equal to the smallest remaining one should be written immediately.