# Using a Robot to Print the Lexicographically Smallest String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string)
Canonical: https://scaleengineer.com/dsa/problems/using-a-robot-to-print-the-lexicographically-smallest-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String, Stack
---
## Problem
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
## Brute-force Simulation
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`.
**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.
**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.
### Explanation
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.

```java
import java.util.Stack;

class Solution {
    public String robotWithString(String s) {
        StringBuilder p = new StringBuilder();
        Stack<Character> t = new Stack<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            t.push(s.charAt(i));

            char minSuffixChar = '{'; // A character larger than 'z'
            if (i + 1 < n) {
                minSuffixChar = s.charAt(i + 1);
                for (int j = i + 2; j < n; j++) {
                    if (s.charAt(j) < minSuffixChar) {
                        minSuffixChar = s.charAt(j);
                    }
                }
            }

            while (!t.isEmpty() && t.peek() <= minSuffixChar) {
                p.append(t.pop());
            }
        }

        while (!t.isEmpty()) {
            p.append(t.pop());
        }

        return p.toString();
    }
}
```
### 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`.

## 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.
**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`.
**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.
### Explanation
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.

```java
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();
    }
}
```
### 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`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  string robotWithString(string s) {
    int cnt[26] = {0};
    for (char &c : s)
      ++cnt[c - 'a'];
    char mi = 'a';
    string stk;
    string ans;
    for (char &c : s) {
      --cnt[c - 'a'];
      while (mi < 'z' && cnt[mi - 'a'] == 0)
        ++mi;
      stk += c;
      while (!stk.empty() && stk.back() <= mi) {
        ans += stk.back();
        stk.pop_back();
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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)

```