Using a Robot to Print the Lexicographically Smallest String

Medium
1241.

Using a Robot to Print the Lexicographically Smallest String

Using a Robot to Print the Lexicographically Smallest String is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.

A robot holds a string t that starts empty, and you are given a string s. Until both s and t are empty, repeatedly perform one of these operations:

  • Remove the first character of s and append it to the end of t.
  • Remove the last character of t and write it on paper.

(t behaves like a stack.) Return the lexicographically smallest string that can end up written on the paper.

Example 1

Input
s = "kairo"
Output
aikor
Explanation
Push `k` and `a`, write `a`; push `i`, write `i` and `k`; push `r` and `o`, write `o` and `r`.

Example 2

Input
s = "zza"
Output
azz
Explanation
Push everything, then write `a`, `z`, `z`.

Example 3

Input
s = "cbca"
Output
acbc

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var robotWithString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Using a Robot to Print the Lexicographically Smallest String Solution

Using a Robot to Print the Lexicographically Smallest String solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Using a Robot to Print the Lexicographically Smallest String is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Greedy, Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A robot holds a string t that starts empty, and you are given a string s. Until both s and t are empty, repeatedly perform one of these operations:

  • Remove the first character of s and append it to the end of t.
  • Remove the last character of t and write it on paper.

(t behaves like a stack.) Return the lexicographically smallest string that can end up written on the paper.

Example 1

Input: s = "kairo"
Output: aikor
Explanation: Push `k` and `a`, write `a`; push `i`, write `i` and `k`; push `r` and `o`, write `o` and `r`.

Example 2

Input: s = "zza"
Output: azz
Explanation: Push everything, then write `a`, `z`, `z`.

Example 3

Input: s = "cbca"
Output: acbc

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only lowercase English letters

Hints for Using a Robot to Print the Lexicographically Smallest String

  1. Hint 1

    The paper should receive the smallest letter available as early as possible.

  2. Hint 2

    Writing the top of t is a good idea when nothing still waiting in s is smaller than it — otherwise you would rather fetch that smaller letter first.

  3. Hint 3

    Keep counts of the letters remaining in s and the smallest of them. After each push, pop while the top of t is at most that smallest remaining letter.

How to solve Using a Robot to Print the Lexicographically Smallest String

Greedy with a stack: after pushing each character, write the top of the stack while it is no larger than the smallest letter still unread in s.

Approach

  1. Count the letters of s; low is the smallest letter with a non-zero count.
  2. For each character of s: push it, decrease its count, and advance low past letters whose count dropped to zero.
  3. While the stack is non-empty and its top is <= low, pop it onto the answer. (Once s is exhausted, low moves past z and everything is popped.)

Why it works

At any moment the next letter written is either the stack's top or some letter still in s (which can only be written after pushing everything in front of it). If the top is no larger than every remaining letter of s, writing it now cannot hurt: any smaller-or-equal letter we might reach later is no better, and delaying it only buries it. If some remaining letter is strictly smaller than the top, writing the top now would put a larger letter where a smaller one could go, so we must keep reading. Ties favour writing, since an equal letter later gains nothing and the written prefix is the same.

Complexity

  • Time — O(n + 26)
  • Space — O(n) for the stack

Pitfalls

  • Compare with the smallest letter still in s (strictly after the current position), not including letters already pushed.
  • Pop on equality (<=), otherwise "zza"-style inputs keep equal letters buried behind larger ones.
  • Recomputing the suffix minimum by scanning is O(n²); keep counts or a suffix-minimum array.

Reference solution

Python

def robotWithString(s: str) -> str:
    cnt = [0] * 26
    for ch in s:
        cnt[ord(ch) - 97] += 1
    low = 0
    stack = []
    out = []
    for ch in s:
        c = ord(ch) - 97
        stack.append(c)
        cnt[c] -= 1
        while low < 26 and cnt[low] == 0:
            low += 1
        while stack and stack[-1] <= low:
            out.append(chr(stack.pop() + 97))
    return "".join(out)

Java

public static String robotWithString(String s) {
    int n = s.length();
    int[] cnt = new int[26];
    for (int i = 0; i < n; i++) cnt[s.charAt(i) - 'a']++;
    char[] st = new char[n];
    int top = 0, low = 0;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        char ch = s.charAt(i);
        st[top++] = ch;
        cnt[ch - 'a']--;
        while (low < 26 && cnt[low] == 0) low++;
        while (top > 0 && st[top - 1] - 'a' <= low) sb.append(st[--top]);
    }
    return sb.toString();
}

C++

string robotWithString(string s) {
    int cnt[26] = {0};
    for (char ch : s) cnt[ch - 'a']++;
    string st, out;
    int low = 0;
    for (char ch : s) {
        st.push_back(ch);
        cnt[ch - 'a']--;
        while (low < 26 && cnt[low] == 0) low++;
        while (!st.empty() && st.back() - 'a' <= low) {
            out.push_back(st.back());
            st.pop_back();
        }
    }
    return out;
}

JavaScript

var robotWithString = function(s) {
    var cnt = new Array(26).fill(0);
    for (var i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
    var low = 0, stack = [], out = [];
    for (var j = 0; j < s.length; j++) {
        var c = s.charCodeAt(j) - 97;
        stack.push(c);
        cnt[c]--;
        while (low < 26 && cnt[low] === 0) low++;
        while (stack.length && stack[stack.length - 1] <= low) out.push(String.fromCharCode(97 + stack.pop()));
    }
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets