Using a Robot to Print the Lexicographically Smallest String

medium stack greedy suffix minimum

Problem

A robot holds an empty string t (a stack). Repeatedly either remove the first character of s and push it onto t, or pop the last character of t and write it on paper. Return the lexicographically smallest string the robot can write.

Inputs = "bdda"

Output"addb"

Push all of "bdda" onto t, then pop everything: a, d, d, b → "addb".

Inputs = "bac"

Output"abc"

Push b, a; pop a, b → "ab"; push c; pop c → "abc".

s (lowercase letters)

def robot_with_string(s):
    n = len(s)
    suffix_min = [0] * (n + 1)
    suffix_min[n] = chr(127)            # sentinel larger than any letter
    for i in range(n - 1, -1, -1):
        suffix_min[i] = min(s[i], suffix_min[i + 1])
    stack, out = [], []
    for i, ch in enumerate(s):
        stack.append(ch)               # push s[i] onto t
        while stack and stack[-1] <= suffix_min[i + 1]:
            out.append(stack.pop())    # write top of t to paper
    while stack:
        out.append(stack.pop())
    return "".join(out)

function robotWithString(s) {
  const n = s.length;
  const suffixMin = new Array(n + 1);
  suffixMin[n] = "{";                  // sentinel after 'z'
  for (let i = n - 1; i >= 0; i--) {
    suffixMin[i] = s[i] < suffixMin[i + 1] ? s[i] : suffixMin[i + 1];
  }
  const stack = [], out = [];
  for (let i = 0; i < n; i++) {
    stack.push(s[i]);                  // push s[i] onto t
    while (stack.length && stack[stack.length - 1] <= suffixMin[i + 1]) {
      out.push(stack.pop());           // write top of t to paper
    }
  }
  while (stack.length) out.push(stack.pop());
  return out.join("");
}

String robotWithString(String s) {
    int n = s.length();
    char[] suffixMin = new char[n + 1];
    suffixMin[n] = '{';                       // sentinel after 'z'
    for (int i = n - 1; i >= 0; i--) {
        char c = s.charAt(i);
        suffixMin[i] = c < suffixMin[i + 1] ? c : suffixMin[i + 1];
    }
    Deque<Character> stack = new ArrayDeque<>();
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < n; i++) {
        stack.push(s.charAt(i));              // push s[i] onto t
        while (!stack.isEmpty() && stack.peek() <= suffixMin[i + 1])
            out.append(stack.pop());          // write top of t
    }
    while (!stack.isEmpty()) out.append(stack.pop());
    return out.toString();
}

string robotWithString(string s) {
    int n = s.size();
    vector<char> suffixMin(n + 1);
    suffixMin[n] = '{';                       // sentinel after 'z'
    for (int i = n - 1; i >= 0; i--)
        suffixMin[i] = min(s[i], suffixMin[i + 1]);
    string stack, out;
    for (int i = 0; i < n; i++) {
        stack.push_back(s[i]);                // push s[i] onto t
        while (!stack.empty() && stack.back() <= suffixMin[i + 1]) {
            out.push_back(stack.back());      // write top of t
            stack.pop_back();
        }
    }
    while (!stack.empty()) { out.push_back(stack.back()); stack.pop_back(); }
    return out;
}

Explanation

The robot's held string t behaves exactly like a stack: characters arrive from the front of s and are pushed on top, and we may only write the most recently pushed (top) character to paper. So the question is purely when to pop.

The greedy rule: pop and write the top of the stack as soon as it is no greater than every character still waiting in s. If something smaller is still coming, we should hold and push it first so it gets written earlier; but once the top is the smallest available character, writing it now is always optimal.

To answer "what is the smallest character still waiting" in O(1), we precompute suffixMin[i] = the minimum of s[i..]. A sentinel suffixMin[n] larger than any letter (we use '{', the byte right after 'z') means "nothing left", so the final flush pops everything.

For each index i we push s[i], then while the stack top is ≤ suffixMin[i+1] (the minimum of the unread suffix) we pop it to the output. After the loop any remaining characters are flushed in stack order.

Each character is pushed once and popped once, so the algorithm runs in linear time. Example s = "bdda": nothing pops while b, d, d sit below the incoming a; once a arrives the stack [b,d,d,a] unwinds to give a, d, d, b = "addb".

Time: O(n) Space: O(n)