Using a Robot to Print the Lexicographically Smallest String

Using a Robot to Print the Lexicographically Smallest String - 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 string s and give it to the robot. The robot will append this character to the string t.
Remove the last character of 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 paper.

Input & Output

Example 1 — Basic Case

$ Input: s = "zab"

› Output: "abz"

💡 Note: Move z to stack, move a to stack, pop a (smaller than remaining min 'b'), move b to stack, pop b, pop z. Result: a + b + z = "abz"

Example 2 — Already Sorted

$ Input: s = "bac"

› Output: "abc"

💡 Note: Move b to stack, move a to stack, pop a (≤ remaining min 'c'), move c to stack, pop c, pop b. Result: a + c + b would be wrong, but we get a, then c when b > c doesn't hold, so abc

Example 3 — Reverse Order

$ Input: s = "cba"

› Output: "abc"

💡 Note: Each character can wait for better ones coming later, resulting in optimal order: abc

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s = 'zab', robot has empty stack t

Process

Use stack + suffix array to make optimal pop decisions

Output

Lexicographically smallest string 'abz'

Key Takeaway

🎯 Key Insight: Use a stack with lookahead - only pop characters when no better option is coming later

Asked in

G Google 15 f Facebook 8

The key insight is to use a stack with lookahead - we can delay popping characters from the stack if better (smaller) characters are coming later. The greedy approach with suffix array preprocessing gives us O(n) time complexity by making optimal decisions about when to output characters. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Sequences	O(2ⁿ)	O(n)	Generate all possible operation sequences and find the lexicographically smallest result
Greedy with Stack and Suffix Array	O(n)	O(n)	Use a stack to store characters and a suffix array to make optimal decisions about when to pop

Brute Force - Try All Sequences — Algorithm Steps

Try moving character from s to t
Try moving character from t to result
Recursively explore all possibilities
Return the lexicographically smallest result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

s='zab', t='', result=''

Branch 1

Move 'z' from s to t

Branch 2

Continue exploring all paths recursively

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* backtrack(const char* s, int sIdx, char* t, int tLen, char* result, int resLen, int sLen) {
    if (sIdx == sLen && tLen == 0) {
        char* final = (char*)malloc((resLen + 1) * sizeof(char));
        strncpy(final, result, resLen);
        final[resLen] = '\0';
        return final;
    }
    
    char* best = NULL;
    
    // Option 1: Move from s to t
    if (sIdx < sLen) {
        t[tLen] = s[sIdx];
        char* newResult = backtrack(s, sIdx + 1, t, tLen + 1, result, resLen, sLen);
        
        if (newResult != NULL) {
            if (best == NULL || strcmp(newResult, best) < 0) {
                if (best != NULL) free(best);
                best = newResult;
            } else {
                free(newResult);
            }
        }
    }
    
    // Option 2: Move from t to result
    if (tLen > 0) {
        char ch = t[tLen - 1];
        result[resLen] = ch;
        char* newResult = backtrack(s, sIdx, t, tLen - 1, result, resLen + 1, sLen);
        
        if (newResult != NULL) {
            if (best == NULL || strcmp(newResult, best) < 0) {
                if (best != NULL) free(best);
                best = newResult;
            } else {
                free(newResult);
            }
        }
    }
    
    return best;
}

char* solution(char* s) {
    int sLen = strlen(s);
    char* t = (char*)malloc((sLen + 1) * sizeof(char));
    char* result = (char*)malloc((sLen + 1) * sizeof(char));
    
    char* answer = backtrack(s, 0, t, 0, result, 0, sLen);
    
    free(t);
    free(result);
    return answer;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

At each step we have 2 choices, leading to exponential possibilities

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and string storage

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Sequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler