The O(n) Club: Backspace String Compare, or: Why Your Undo Key Hates You

The O(n) Club: Backspace String Compare, or: Why Your Undo Key Hates You

⚡ TL;DR

You have two strings, both infected with more ‘#’ than a late-night Slack chat. Each ‘#’ erases the character before it. Your job: Simulate the backspaces and decide if both strings end up identical. The “let’s not think” method builds the result using a stack and compares:

public boolean backspaceCompare(String s, String t) {
    return build(s).equals(build(t));
}
private String build(String str) {
    StringBuilder sb = new StringBuilder();
    for (char c : str.toCharArray()) {
        if (c == '#') {
            if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}

🧠 How Devs Usually Mess This Up

First instinct: just delete the ‘#’s! Second instinct: try to be clever and “fix” the string in place, left-to-right, then stare in horror as your code erases the wrong stuff, gets lost in consecutive backspaces, and skips all edge cases. Bonus: Many attempts simply do replaceAll(“#”, “”) which is cute, but unfortunately treats backspaces as stickers, not bulldozers. Go on, test with “####” and watch your logic unravel faster than your sleep schedule.

🔍 What’s Actually Going On

Think of your string like a hyperactive kindergartner at a chalkboard: every ‘#’ means erasing the last thing you drew. Since typing from the start gets messy (how do you erase what’s not yet there?), it’s smarter to build from scratch with a stack (press, erase, repeat), or just moonwalk backwards with two pointers, skipping all doomed characters. Both ways, the idea is this: when a ‘#’ hits, pop the previous entry—or if there’s nothing, just pretend you’re the backspace key on a fresh Google Doc (does. absolutely. nothing.).

🛠️ PseudoCode

• Stack method:
  • Create an empty stack for each string
  • For every char:
    • If it’s ‘#’, pop from stack (if not empty)
    • Else, push to stack
  • Join everything in the stack for final answer

  private String build(String s) {
      Stack
  <character> stack = new Stack<>();
      for (char c : s.toCharArray()) {
          if (c == '#') {
              if (!stack.isEmpty()) stack.pop();
          } else {
              stack.push(c);
          }
      }
      StringBuilder sb = new StringBuilder();
      while (!stack.isEmpty()) sb.insert(0, stack.pop());
      return sb.toString();
  }</character>

• Ultra-light, pro-interviewer two-pointer method:
  • Work backwards in both strings
  • Track how many characters to skip (for ‘#’)
  • Skip as needed, compare what’s left

  // See Below for Implementation!

💻 The Code

// Two-pointer, memory-hermit edition
default boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skipS = 0, skipT = 0;
    while (i >= 0 || j >= 0) {
        // For s
        while (i >= 0) {
            if (s.charAt(i) == '#') { skipS++; i--; }
            else if (skipS > 0) { skipS--; i--; }
            else break;
        }
        // For t
        while (j >= 0) {
            if (t.charAt(j) == '#') { skipT++; j--; }
            else if (skipT > 0) { skipT--; j--; }
            else break;
        }
        // Compare
        if (i >= 0 && j >= 0) {
            if (s.charAt(i) != t.charAt(j)) return false;
        } else {
            if (i >= 0 || j >= 0) return false;
        }
        i--; j--;
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Too many backspaces? It’s fine, your string is now a void. Embrace the nothingness.
• Starting with loads of ‘#’: “#####abc” means all those hashtags are harmless—nothing to erase—so skip ’em.
• Brute stack = O(n) space, Two pointers = O(1) space: Impress your interviewer by actually mentioning the tradeoff.
• If working left-to-right, expect accidental time travel and a broken string as a reward.

🧠 Interviewer Brain-Tattoo

“Backspaces remove mistakes in your strings, not in your thinking. Code like you test: mercilessly.”