Scale Engineer

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 TableStringStack

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 <= 105
  • 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.

import java.util.Stack; class Solution {    public String robotWithString(String s) {        int n = s.length();        StringBuilder p = new StringBuilder();        Stack<Character> t = new Stack<>();         // Pre-compute suffix minimums        char[] suffixMin = new char[n];        suffixMin[n - 1] = s.charAt(n - 1);        for (int i = n - 2; i >= 0; i--) {            suffixMin[i] = (char) Math.min(s.charAt(i), suffixMin[i + 1]);        }         for (int i = 0; i < n; i++) {            t.push(s.charAt(i));                        char minCharInRest = (i + 1 < n) ? suffixMin[i + 1] : '{'; // '{' is > 'z'             while (!t.isEmpty() && t.peek() <= minCharInRest) {                p.append(t.pop());            }        }         while (!t.isEmpty()) {            p.append(t.pop());        }         return p.toString();    }}

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.

Solutions

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

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 →

Next problem