The O(n) Club: Remove Duplicate Letters: Stack Attacks and Lex Wins

The O(n) Club: Remove Duplicate Letters—Stack Attacks and Lex Wins

⚡ TL;DR

Want one of each letter from your string, perfectly alphabetized? Brute force is like hunting for a typo in War and Peace using only a torch and hope. Go greedy and stacky instead:

// Brute force (don't!)
// Try all subsequences, keep unique ones, grab smallest. Runs in exponential time. 
// Real-life performance: About as fast as waiting for bread to un-toast itself.

🧠 How Devs Usually Mess This Up

If you’ve ever tossed the letters in a Set, sorted it, and hit submit—congrats: you just missed the point. Order matters! The interviewer isn’t looking for Set-uniqueness—they want you to give them the smallest word possible, not just any arrangement. ‘abc’ ≠ ‘bac’; if you don’t keep order, you get the wrong flavor of alphabet soup.

🔍 What’s Actually Going On

This beast mixes a greedy approach (snatch the smallest letter when you can) with a monotonic stack (only let the right stuff stay on top). Picture auditioning singers: you want a unique, perfectly ordered set, and if someone with a better voice comes in but the band leader can still return later, you boot the old leader for now. With one eye on lex order and the other on future appearances, you pop and push till your stack is ready for Broadway (or LeetCode).

🛠️ PseudoCode

• Track last seen: For each letter, record the last index it appears at in the string.
  // int[] last = new int[26];
• Iterate the string: For each character…
  • If already in your result (stack), skip. No reruns.
  • While stack isn’t empty and top of stack is bigger (worse) than the current letter and you know you’ll see that bigger letter again, pop it off. You’re making room for a better auditionee.
  • Add the current letter to the stack, and mark it as ‘in stack’ so you won’t add it again.
• Join the stack together for the final answer. Applause.

💻 The Code

import java.util.*;
public class RemoveDuplicateLetters {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        boolean[] seen = new boolean[26];
        Deque
<character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a';
            if (seen[idx]) continue;
            while (!stack.isEmpty() && c < stack.peekLast() && last[stack.peekLast() - 'a'] > i) {
                seen[stack.pollLast() - 'a'] = false;
            }
            stack.addLast(c);
            seen[idx] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) sb.append(ch);
        return sb.toString();
    }
}
</character>

⚠️ Pitfalls, Traps & Runtime Smacks

• Single Appearance Letters: Don’t pop what can’t come back—letters appearing once must stay, or they’re gone for good.
• Seen/Unseen Confusion: Forget to toggle ‘seen’ when popping? Welcome to duplicate city.
• Order Paranoia: Sorting at the end? Nope, that’s not just forbidden—it’s wrong.
• O(n) time and space: smooth for interviews, friendly to CPUs. Everyone’s happy, even your RAM.

🧠 Interviewer Brain-Tattoo

“If you think removing duplicates is just Set logic, you’ll never make it past round one—this is musical chairs, but only the right letter gets the last seat.”