🤖 Greedy Robot & Lexicographically Smallest String | LeetCode 2434 (C++ | JavaScript

Hey, tech explorers! 🌟 Today, let’s dive into a fun and slightly sneaky greedy problem — LeetCode 2434: Using a Robot to Print the Lexicographically Smallest String. We'll crack it open using an intuitive stack-based greedy approach. 💡

📜 Problem Overview

You're given a string s, and a robot holding an empty string t. The robot can:

Remove the first character from s and append it to t.
Remove the last character from t and write it onto paper.

You keep performing these operations until both s and t are empty.

📝 Goal: Return the lexicographically smallest string that can be written on paper.

🧠 Intuition

We need to cleverly decide when to pop from t and write to the paper so the final string is smallest in order. The key:

Maintain the minimum character ahead of each position in s.
Use a stack to simulate t.
Whenever the top of t is smaller than or equal to the minimum future character in s, we pop it to the output.

⚙️ C++ Code (Optimized)

char t[100000], xMin[100000];
int top=-1;
class Solution {
public:
    static string robotWithString(string& s) {
        int freq[26]={0}, n=s.size();
        xMin[n-1]=s.back();
        for(int i=n-2; i>=0; i--)
            xMin[i]=min(s[i], xMin[i+1]);

        string p;
        top=-1;
        p.reserve(n);
        for(int i=0; i<n; i++){
            t[++top]=s[i];
            while(top!=-1 && (i==n-1 || t[top]<=xMin[i+1])){
                p+=t[top--];
            }
        }
        return p;
    }
};

🌐 JavaScript Version

var robotWithString = function(s) {
    let n = s.length;
    let minChar = Array(n);
    minChar[n - 1] = s[n - 1];

    for (let i = n - 2; i >= 0; i--) {
        minChar[i] = s[i] < minChar[i + 1] ? s[i] : minChar[i + 1];
    }

    let t = [], result = [];
    for (let i = 0; i < n; i++) {
        t.push(s[i]);
        while (t.length && (i === n - 1 || t[t.length - 1] <= minChar[i + 1])) {
            result.push(t.pop());
        }
    }

    return result.join("");
};

🐍 Python Version

def robotWithString(s: str) -> str:
    n = len(s)
    min_char = [''] * n
    min_char[-1] = s[-1]

    for i in range(n - 2, -1, -1):
        min_char[i] = min(s[i], min_char[i + 1])

    stack = []
    result = []

    for i in range(n):
        stack.append(s[i])
        while stack and (i == n - 1 or stack[-1] <= min_char[i + 1]):
            result.append(stack.pop())

    return ''.join(result)

🧪 Test Cases

Input: s = "zza"
Output: "azz"
Explanation: We take all into t, then pop in order.

Input: s = "bac"
Output: "abc"
Explanation: b->t, a->t, then pop both.

Input: s = "bdda"
Output: "addb"
Explanation: All go to t first, then stack unwinds.

// 🔥 Unique Edge Test Cases
Input: s = "cbaaa"
Output: "aaabc"  // Stack builds up then spills smallest chars

Input: s = "zyxwvutsrqponmlkjihgfedcba"
Output: "abcdefghijklmnopqrstuvwxyz" // Perfectly reverse, full stack build

🧮 Time & Space Complexity

Time Complexity: O(n)  // Each character is pushed and popped at most once
Space Complexity: O(n) // Stack and min-array of size n

✨ Wrap Up

This problem beautifully blends greedy logic with stack simulation! Perfect for interviews and leveling up your string intuition. 📈

If you found this helpful, smash that ❤️ and follow for more intuitive breakdowns!

Happy coding! 🚀💻

Om Shree @om_shree_0709