Using a Robot to Print the Lexicographically Smallest String

Medium Monotonic Stack Monotonic Stack Original on LeetCode

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 s and append it to the end of t, or
  • take the last character of t and 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^5
  • s contains 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (try every order of moves)ExponentialO(n²)
Optimal (stack + suffix minimum)O(n)O(n)

1Brute force (try every order of moves)

TimeExponentialThe number of move orders grows like the Catalan numbers.
SpaceO(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.

  1. best(i, t): if i == n and t is empty, return "".
  2. Option 1 (if i < n): best(i + 1, t + s[i]).
  3. Option 2 (if t is not empty): last letter of t + best(i, t without its last letter).
  4. 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;
    }
}

2Optimal (stack + suffix minimum)

TimeO(n)Each letter is pushed once and popped once.
SpaceO(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.

  1. minRight[n] = a sentinel larger than 'z'; minRight[i] = min(s[i], minRight[i + 1]).
  2. For each i: push s[i]; while the stack is not empty and top <= minRight[i + 1], pop and append to the answer.
  3. 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();
    }
}

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.