Using a Robot to Print the Lexicographically Smallest String

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^5
• s consists of only English lowercase letters.

## Lexicographically Smallest String from Robot Operations

This problem involves finding the lexicographically smallest string that can be formed by strategically moving characters between a string `s`, a robot's holding string `t`, and the final paper.

### 1. Brute Force (Inefficient)

A brute-force approach would involve exploring all possible combinations of operations (moving a character from `s` to `t`, or from `t` to the paper). However, this leads to exponential time complexity and is not practical for larger inputs.

### 2. Optimal Solution (Greedy with Suffix Minimum)

The key idea is to use a greedy approach combined with pre-computation of suffix minimums in `s`. We iterate through `s`, and for each character, we decide whether to move it to `t` or to directly write characters from `t` to the paper. We prioritize writing from `t` to the paper if it results in a lexicographically smaller string.

**Algorithm:**

1.  **Precompute Suffix Minimum:** Create an array `suffixMin` where `suffixMin[i]` stores the minimum character in the suffix `s[i:]`.
2.  **Iterate Through `s`:**
    *   For each character `s[i]`, move it from `s` to `t`.
    *   While `t` is not empty and the last character of `t` is less than or equal to the minimum character in the remaining suffix of `s` (i.e., `suffixMin[i+1]` if `i+1` is within bounds, otherwise some large character), pop the last character from `t` and append it to the paper.
3.  **Empty `t`:** After processing `s`, empty `t` by appending its characters to the paper.
4.  Return the paper string.

**Example:**

`s = "bac"`

1.  `suffixMin = ['a', 'a', 'c']`
2.  **Iteration 1 (i=0, s[0]='b'):**
    *   Move 'b' to `t`: `t = "b"`
    *   `t[-1] = 'b' > suffixMin[1] = 'a'`, so do nothing.
3.  **Iteration 2 (i=1, s[1]='a'):**
    *   Move 'a' to `t`: `t = "ba"`
    *   `t[-1] = 'a' <= suffixMin[2] = 'c'`, so move 'a' to paper: `paper = "a", t = "b"`
    *   `t[-1] = 'b' > suffixMin[2] = 'c'`, so do nothing.
4.  **Iteration 3 (i=2, s[2]='c'):**
    *   Move 'c' to `t`: `t = "bc"`
    *   `t[-1] = 'c' <= large_char`, so move 'c' to paper: `paper = "ac", t = "b"`
    *   `t[-1] = 'b' <= large_char`, so move 'b' to paper: `paper = "acb", t = ""`
5.  `paper = "abc"`

```python
def robot_string(s):
    n = len(s)
    suffix_min = [''] * n
    suffix_min[n - 1] = s[n - 1]
    for i in range(n - 2, -1, -1):
        suffix_min[i] = min(s[i], suffix_min[i + 1])

    t = ""
    paper = ""
    for i in range(n):
        t += s[i]
        while t and (i == n - 1 or t[-1] <= suffix_min[i + 1]):
            paper += t[-1]
            t = t[:-1]

    paper += t[::-1]
    return paper

# Example Usage
s1 = "zza"
print(f"{s1=}, {robot_string(s1)=}")

s2 = "bac"
print(f"{s2=}, {robot_string(s2)=}")

s3 = "bdda"
print(f"{s3=}, {robot_string(s3)=}")

3. Big(O) Time Complexity Analysis

The most time-consuming part of the algorithm is the initial computation of the suffix minimum array, which takes O(n) time, where n is the length of the string s. The main loop iterates through s once (O(n)), and the inner while loop, in the worst-case scenario, can iterate up to n times in total across all iterations of the outer loop (because each character of s is added to and removed from t at most once). Therefore, the overall time complexity is dominated by O(n).

4. Big(O) Space Complexity Analysis

The space complexity is primarily determined by the suffix_min array, which requires O(n) space. The t string can also grow up to size n in the worst case. The paper string can also grow to size n. Therefore, the overall space complexity is O(n).

5. Edge Cases

• Empty Input String: If s is empty, the algorithm should return an empty string. This is handled correctly by the provided code.
• String with Identical Characters: If s contains only identical characters (e.g., "aaaa"), the algorithm will correctly produce the sorted string "aaaa".
• Lexicographically Sorted String: If s is already lexicographically sorted (e.g., "abc"), the algorithm will also produce "abc".
• Reverse Sorted String: If s is reverse sorted, (e.g. "cba"), the algorithm will produce "abc".