Using a Robot to Print the Lexicographically Smallest String

MEDIUM

Description

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

Checkout 2 different approaches to solve Using a Robot to Print the Lexicographically Smallest String. Click on different approaches to view the approach and algorithm in detail.

Optimized Greedy with Suffix Minimums

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.

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 Analysis

Time Complexity: 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 Complexity: O(n). We use `O(n)` space for the `suffixMin` array, `O(n)` for the stack `t`, and `O(n)` for the result `StringBuilder`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Using a Robot to Print the Lexicographically Smallest String. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Using a Robot to Print the Lexicographically Smallest String

Patterns:

Greedy

Data Structures:

Hash TableStringStack