Using a Robot to Print the Lexicographically Smallest String

Med

#2218Time: O(n). Pre-computation takes `O(n)`. The main simulation loop involves `n` pushes and `n` pops in total, making it `O(n)`. The total complexity is linear.Space: O(n). We use `O(n)` space for the `suffixMin` array, `O(n)` for the stack `t`, and `O(n)` for the result `StringBuilder`.

Patterns

Greedy

Data structures

Hash Table String Stack

Prompt

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 <= 10⁵
s consists of only English lowercase letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach enhances the greedy simulation by pre-calculating the minimum character for all suffixes of the input string s. This optimization eliminates the need for repeated scans of s, reducing the time complexity from quadratic to linear.

Algorithm

Create an array suffixMin of the same size as s.
Populate suffixMin by iterating from right to left: suffixMin[i] = min(s.charAt(i), suffixMin[i+1]).
Initialize an empty StringBuilder p and an empty Stack t.
Loop through each character s[i] of the input string s.
Push s[i] onto the stack t.
Get the minimum of the remaining part of s by looking up suffixMin[i+1] (or use a placeholder if at the end).
While the stack t is not empty and t.peek() is less than or equal to this minimum:
- Pop a character from t and append it to p.
After the loop, pop any remaining characters from t and append them to p.
Return the string from p.

Walkthrough

The core greedy strategy is maintained: process s from left to right using a stack t, and pop from t whenever its top element is less than or equal to the smallest character yet to be processed in s. To make this check efficient, we first create a suffixMin array. suffixMin[i] stores the minimum character in the substring s from index i to the end. This array is computed in O(n) time with a single pass from right to left. With this pre-computed data, finding the minimum character in the rest of the string (s[i+1...]) becomes an O(1) lookup (suffixMin[i+1]). The main simulation then proceeds, with each character being pushed and popped from the stack at most once, resulting in an overall linear time complexity.

1import java.util.Stack;2 3class Solution {4    public String robotWithString(String s) {5        int n = s.length();6        StringBuilder p = new StringBuilder();7        Stack<Character> t = new Stack<>();8 9        // Pre-compute suffix minimums10        char[] suffixMin = new char[n];11        suffixMin[n - 1] = s.charAt(n - 1);12        for (int i = n - 2; i >= 0; i--) {13            suffixMin[i] = (char) Math.min(s.charAt(i), suffixMin[i + 1]);14        }15 16        for (int i = 0; i < n; i++) {17            t.push(s.charAt(i));18            19            char minCharInRest = (i + 1 < n) ? suffixMin[i + 1] : '{'; // '{' is > 'z'20 21            while (!t.isEmpty() && t.peek() <= minCharInRest) {22                p.append(t.pop());23            }24        }25 26        while (!t.isEmpty()) {27            p.append(t.pop());28        }29 30        return p.toString();31    }32}

Complexity

Time

O(n). Pre-computation takes `O(n)`. The main simulation loop involves `n` pushes and `n` pops in total, making it `O(n)`. The total complexity is linear.

Space

O(n). We use `O(n)` space for the `suffixMin` array, `O(n)` for the stack `t`, and `O(n)` for the result `StringBuilder`.

Trade-offs

Pros

Optimal time complexity, efficient for large inputs and passes all constraints.

Cons

Requires additional O(n) space for the pre-computed suffix minimums array.

This approach directly simulates the process. At each step, a greedy decision is made: either move a character from the input string s to a temporary stack t, or print a character from t. The decision to print from t is made if its top character is smaller than or equal to any character remaining in s. This requires repeatedly scanning the rest of s.

Algorithm

Initialize an empty StringBuilder p and an empty Stack t.
Loop through each character s[i] of the input string s.
Push s[i] onto the stack t.
Find the minimum character min_char in the suffix s[i+1...]. If the suffix is empty, use a placeholder character larger than 'z'.
While the stack t is not empty and t.peek() <= min_char:
- Pop a character from t and append it to p.
After the loop, pop any remaining characters from t and append them to p.
Return the string from p.

Walkthrough

We iterate through the input string s, character by character. For each character, we push it onto a stack t. After each push, we check if we can print from the stack. The greedy choice is to print the character at the top of the stack if it's no larger than the smallest character in the unprocessed part of s. To implement this check, we perform a linear scan of the suffix of s to find its minimum element. This process is repeated: while the stack is not empty and its top is less than or equal to the minimum of the remaining part of s, we pop from the stack and append to our result. After s is fully processed, any characters left in the stack are appended to the result. The main drawback is the repeated scanning of s, which leads to a quadratic time complexity.

1import java.util.Stack;2 3class Solution {4    public String robotWithString(String s) {5        StringBuilder p = new StringBuilder();6        Stack<Character> t = new Stack<>();7        int n = s.length();8 9        for (int i = 0; i < n; i++) {10            t.push(s.charAt(i));11 12            char minSuffixChar = '{'; // A character larger than 'z'13            if (i + 1 < n) {14                minSuffixChar = s.charAt(i + 1);15                for (int j = i + 2; j < n; j++) {16                    if (s.charAt(j) < minSuffixChar) {17                        minSuffixChar = s.charAt(j);18                    }19                }20            }21 22            while (!t.isEmpty() && t.peek() <= minSuffixChar) {23                p.append(t.pop());24            }25        }26 27        while (!t.isEmpty()) {28            p.append(t.pop());29        }30 31        return p.toString();32    }33}

Complexity

Time

O(n^2), where n is the length of the string `s`. The outer loop runs `n` times, and inside it, finding the minimum character in the suffix of `s` takes up to O(n) time.

Space

O(n). The stack `t` and the result `StringBuilder` `p` can each store up to `n` characters.

Trade-offs

Pros

Conceptually simple and directly follows the greedy logic of the problem.

Cons

Inefficient due to the O(n^2) time complexity, making it unsuitable for large inputs and likely to cause a 'Time Limit Exceeded' error.

Solutions

Solution

1class Solution {2public3  String robotWithString(String s) {4    int[] cnt = new int[26];5    for (char c : s.toCharArray()) {6      ++cnt[c - 'a'];7    }8    StringBuilder ans = new StringBuilder();9    Deque<Character> stk = new ArrayDeque<>();10    char mi = 'a';11    for (char c : s.toCharArray()) {12      --cnt[c - 'a'];13      while (mi < 'z' && cnt[mi - 'a'] == 0) {14        ++mi;15      }16      stk.push(c);17      while (!stk.isEmpty() && stk.peek() <= mi) {18        ans.append(stk.pop());19      }20    }21    return ans.toString();22  }23}

1class Solution {2public:3  string robotWithString(string s) {4    int cnt[26] = {0};5    for (char &c : s)6      ++cnt[c - 'a'];7    char mi = 'a';8    string stk;9    string ans;10    for (char &c : s) {11      --cnt[c - 'a'];12      while (mi < 'z' && cnt[mi - 'a'] == 0)13        ++mi;14      stk += c;15      while (!stk.empty() && stk.back() <= mi) {16        ans += stk.back();17        stk.pop_back();18      }19    }20    return ans;21  }22};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem