The O(n) Club: Remove All Adjacent Duplicates in String — Now With 100% Less Regret Than Brute Force

The O(n) Club: Remove All Adjacent Duplicates in String — Now With 100% Less Regret Than Brute Force

⚡ TL;DR

Stuck deleting every pair of adjacent clones in a string? Scanning, cutting, and re-scanning is a one-way ticket to O(n²) sadness. Use a stack — or, for the fancy folks, a StringBuilder as a stack. Each char goes in; if it’s a twin, both bail. One pass, O(n), no infinite loop nightmares. See?

// Java stack-style, but cooler
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
    int len = sb.length();
    if (len > 0 && sb.charAt(len - 1) == c) {
        sb.deleteCharAt(len - 1);
    } else {
        sb.append(c);
    }
}
return sb.toString();

🧠 How Devs Usually Mess This Up

Common story: you walk in thinking one scan is enough. “Remove aa and I’m done, right?” Wrong. Removing a pair might create new pairs, like whack-a-mole for keyboard typos. If you try rescanning every time, enjoy your O(n²) runtime and existential dread. And no, k-group removals (that’s 1209, pal) are a totally different beast — here, “pair” literally means two. Don’t get greedy.

🔍 What’s Actually Going On

This is a party—every character lines up at the velvet rope, the bouncer (your stack) checks if they look suspiciously familiar. If they’re identical to the previous guest, out they both go. If not, in they go. No reruns, no do-overs. By closing time? Only the characters with no adjacent twins are left hanging around. Thanks, Stack Security!

🛠️ PseudoCode

• Initialize your stack:
  StringBuilder sb = new StringBuilder();
  (No actual Stack class embarrassment required.)
• Loop through each character in the input:
  for (char c : s.toCharArray())
• If the last character on the stack matches the current, remove it:
  if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c)
• If not, add this character to the stack:
  else sb.append(c);
• At the end, convert the stack to a string and return:
  return sb.toString();

💻 The Code

public String removeDuplicates(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        int len = sb.length();
        if (len > 0 && sb.charAt(len - 1) == c) {
            sb.deleteCharAt(len - 1);
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• “balllloon”: New pairs can pop up after you remove one, so don’t expect to finish in one pass if you go brute force.
• Punishing O(n²): Naive scan/delete/scan wastes your laptop’s precious years. Stack saves you a therapist’s bill.
• Space/Time: It’s O(n) either way (all chars go on/off the stack once). In-place pointer tricks exist but don’t change the math for interviews.
• This isn’t the “k duplicates” version: No, you can’t flex your k-group muscles here.

🧠 Interviewer Brain-Tattoo

“If you’re deleting pairs in a string and you’re not using a stack, you’re basically washing dishes with a toothbrush. Stack up, my friend.”