103. Backspace String Compare

🔗 LeetCode Problem: 844. Backspace String Compare
📊 Difficulty: Easy
🏷️ Topics: Stack, String, Two Pointers, Simulation

Problem Statement

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true

Explanation: 
Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true

Explanation: 
Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false

Explanation: 
s becomes "c" while t becomes "b".

Constraints: - 1 <= s.length, t.length <= 200 - s and t only contain lowercase letters and '#' characters.

Follow-up: Can you solve it in O(n) time and O(1) space?

🌟 ELI5: The Simple Idea!

Think of typing with backspace key:

Type: "abc"
  Screen: "abc"

Type: "ab#c"
  a → Screen: "a"
  b → Screen: "ab"
  # → Screen: "a"    (backspace deleted 'b')
  c → Screen: "ac"

Compare "abc" vs "ab#c":
  "abc" → "abc"
  "ab#c" → "ac"
  Not equal!

The Stack Analogy:

Typing is like a stack:
  - Letter: Push to stack
  - Backspace (#): Pop from stack

"ab#c":
  'a' → stack: [a]
  'b' → stack: [a, b]
  '#' → stack: [a]      (pop 'b')
  'c' → stack: [a, c]

Result: "ac" ✓

🎨 Visual Understanding

Example 1: Equal Strings

s = "ab#c"
t = "ad#c"

═══════════════════════════════════════════════════════════════
Process s = "ab#c"
═══════════════════════════════════════════════════════════════

Char: 'a'
  Not '#' → Add to result
  Stack: [a]

Char: 'b'
  Not '#' → Add to result
  Stack: [a, b]

Char: '#'
  Backspace → Remove last character
  Stack: [a]

Char: 'c'
  Not '#' → Add to result
  Stack: [a, c]

Result: "ac"

═══════════════════════════════════════════════════════════════
Process t = "ad#c"
═══════════════════════════════════════════════════════════════

Char: 'a'
  Stack: [a]

Char: 'd'
  Stack: [a, d]

Char: '#'
  Stack: [a]

Char: 'c'
  Stack: [a, c]

Result: "ac"

═══════════════════════════════════════════════════════════════
Compare
═══════════════════════════════════════════════════════════════

s result: "ac"
t result: "ac"
Equal? Yes ✓

Return: true

Example 2: Both Become Empty

s = "ab##"
t = "c#d#"

Process s:
  'a' → [a]
  'b' → [a, b]
  '#' → [a]
  '#' → []
  Result: ""

Process t:
  'c' → [c]
  '#' → []
  'd' → [d]
  '#' → []
  Result: ""

Compare: "" == "" ✓
Return: true

🎯 Approach 1: Stack ⭐

The Intuitive Solution

Algorithm:

1. Build final string for s using stack
2. Build final string for t using stack
3. Compare the two final strings

For each string:
  - If character is '#': pop from stack (if not empty)
  - Otherwise: push character to stack

Implementation

/**
 * Stack-based approach
 * Time: O(n + m), Space: O(n + m)
 */
public boolean backspaceCompare(String s, String t) {
    return buildString(s).equals(buildString(t));
}

private String buildString(String str) {
    Stack<Character> stack = new Stack<>();

    for (char c : str.toCharArray()) {
        if (c == '#') {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else {
            stack.push(c);
        }
    }

    // Convert stack to string
    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }

    return sb.toString();
}

⏰ Time: O(n + m) where n = s.length, m = t.length
💾 Space: O(n + m) for stacks and strings

Alternative: Using StringBuilder

private String buildString(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();
}

StringBuilder acts like a stack here!

🎯 Approach 2: Two Pointers (O(1) Space) ⭐⭐

The Optimal Solution

Algorithm:

Process strings from RIGHT to LEFT:
  - Backspace affects characters to the LEFT
  - Easier to skip characters going backwards

For each string:
  1. Start from end
  2. Count backspaces (#)
  3. Skip characters based on backspace count
  4. Find next valid character
  5. Compare valid characters

Implementation

/**
 * Two pointers from right to left
 * Time: O(n + m), Space: O(1)
 */
public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1;
    int j = t.length() - 1;

    while (i >= 0 || j >= 0) {
        // Find next valid character in s
        i = getNextValidIndex(s, i);

        // Find next valid character in t
        j = getNextValidIndex(t, j);

        // Both exhausted
        if (i < 0 && j < 0) {
            return true;
        }

        // One exhausted, other not
        if (i < 0 || j < 0) {
            return false;
        }

        // Compare characters
        if (s.charAt(i) != t.charAt(j)) {
            return false;
        }

        // Move to next
        i--;
        j--;
    }

    return true;
}

private int getNextValidIndex(String str, int index) {
    int backspaces = 0;

    while (index >= 0) {
        if (str.charAt(index) == '#') {
            backspaces++;
            index--;
        } else if (backspaces > 0) {
            backspaces--;
            index--;
        } else {
            break;  // Found valid character
        }
    }

    return index;
}

⏰ Time: O(n + m)
💾 Space: O(1) - Only variables, no extra data structures

🔍 Super Detailed Dry Run (Two Pointers)

Example: s = "ab#c", t = "ad#c"

Goal: Compare final strings without building them

═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════

s = "ab#c"  (indices: 0,1,2,3)
t = "ad#c"  (indices: 0,1,2,3)

i = 3 (end of s)
j = 3 (end of t)

═══════════════════════════════════════════════════════════════
Iteration 1
═══════════════════════════════════════════════════════════════

Find next valid in s starting from i=3:
  getNextValidIndex(s, 3):
    index = 3, char = 'c'
    Not '#', backspaces = 0
    Found valid at index 3
  Return: 3

Find next valid in t starting from j=3:
  getNextValidIndex(t, 3):
    index = 3, char = 'c'
    Not '#', backspaces = 0
    Found valid at index 3
  Return: 3

Compare:
  i = 3, j = 3
  s[3] = 'c', t[3] = 'c'
  Match! ✓

Move to next:
  i = 2, j = 2

═══════════════════════════════════════════════════════════════
Iteration 2
═══════════════════════════════════════════════════════════════

Find next valid in s starting from i=2:
  getNextValidIndex(s, 2):
    index = 2, char = '#'
    It's '#' → backspaces = 1, index = 1

    index = 1, char = 'b'
    Not '#', backspaces = 1 > 0
    Skip this char → backspaces = 0, index = 0

    index = 0, char = 'a'
    Not '#', backspaces = 0
    Found valid at index 0
  Return: 0

Find next valid in t starting from j=2:
  getNextValidIndex(t, 2):
    index = 2, char = '#'
    It's '#' → backspaces = 1, index = 1

    index = 1, char = 'd'
    Not '#', backspaces = 1 > 0
    Skip this char → backspaces = 0, index = 0

    index = 0, char = 'a'
    Not '#', backspaces = 0
    Found valid at index 0
  Return: 0

Compare:
  i = 0, j = 0
  s[0] = 'a', t[0] = 'a'
  Match! ✓

Move to next:
  i = -1, j = -1

═══════════════════════════════════════════════════════════════
Loop Exit
═══════════════════════════════════════════════════════════════

Condition: i >= 0 || j >= 0
  -1 >= 0 || -1 >= 0 → false

Exit loop

Check: i < 0 && j < 0
  true ✓

Return: true

Result: Strings are equal after backspaces! ✓

Example 2: s = "a#c", t = "b" (Not Equal)

s = "a#c", t = "b"

i = 2, j = 0

Iteration 1:
  getNextValidIndex(s, 2):
    index = 2, 'c' → valid at 2

  getNextValidIndex(t, 0):
    index = 0, 'b' → valid at 0

  Compare: s[2]='c', t[0]='b'
  'c' != 'b' ✗

Return: false

🎯 Why Two Pointers Works

The Right-to-Left Insight

Why process backwards?

Forward (Hard):
  "ab#c"
  Need to remember to delete 'b' later
  Requires lookahead or building result

Backward (Easy):
  "ab#c"
      ↑
  Start from 'c' → valid
  Move to '#' → skip next char
  Skip 'b', find 'a' → valid

  No building needed!

The Backspace Logic

When going backward:

See '#':
  backspaces++
  Skip this position

See regular char:
  If backspaces > 0:
    Skip this char (it's deleted)
    backspaces--
  Else:
    This is valid char!
    Stop here

Example: "ab#c"
         01 2 3

From index 3:
  3: 'c' → backspaces=0 → valid
From index 2:
  2: '#' → backspaces=1
  1: 'b' → backspaces>0 → skip, backspaces=0
  0: 'a' → backspaces=0 → valid

⚠️ Common Mistakes

Mistake 1: Not checking empty before pop

// ❌ WRONG - EmptyStackException
if (c == '#') {
    stack.pop();  // What if stack is empty?
}

// ✓ CORRECT - Check first
if (c == '#') {
    if (!stack.isEmpty()) {
        stack.pop();
    }
}

Mistake 2: Building result in wrong order (stack)

// ❌ WRONG - Stack is LIFO!
String result = "";
while (!stack.isEmpty()) {
    result += stack.pop();  // Reversed!
}

// ✓ CORRECT - Iterate normally or reverse
StringBuilder sb = new StringBuilder();
for (char c : stack) {
    sb.append(c);  // Correct order
}

Mistake 3: Two pointers - wrong termination condition

// ❌ WRONG - AND instead of OR
while (i >= 0 && j >= 0) {
    // Stops when one exhausted, but other might have chars

// ✓ CORRECT - Continue while either has chars
while (i >= 0 || j >= 0) {

Mistake 4: Not handling different lengths

// ❌ WRONG - Assumes same length
if (i < 0 && j < 0) return true;
return false;  // What if i < 0 but j >= 0?

// ✓ CORRECT - Check both exhausted
if (i < 0 && j < 0) return true;
if (i < 0 || j < 0) return false;  // One exhausted

Mistake 5: Comparing indices instead of characters

// ❌ WRONG - Comparing positions!
if (i != j) return false;

// ✓ CORRECT - Compare actual characters
if (s.charAt(i) != t.charAt(j)) return false;

🎯 Pattern Recognition

Problem Type: String Processing with Backspace
Core Pattern: Stack Pattern 2 - String Processing

When to Apply:
✓ Character-by-character processing
✓ Backspace/delete operations
✓ Build final string from operations
✓ Compare processed strings

Recognition Keywords:
- "backspace"
- "delete"
- "typing"
- "text editor"
- "#" means delete

Similar Problems:
- Remove All Adjacent Duplicates (LC 1047)
- Make String Great (LC 1544)
- Removing Stars From a String (LC 2390)
- Crawler Log Folder (LC 1598)

Key Components:
┌────────────────────────────────────────────┐
│ Stack: Build final string                 │
│ Regular char: Push to stack               │
│ '#': Pop from stack (if not empty)       │
│ Compare: Built strings                    │
│ Optimal: Two pointers O(1) space         │
│ Time: O(n+m), Space: O(n+m) or O(1)      │
└────────────────────────────────────────────┘

🧠 Interview Strategy

Step 1: "This is a string processing with backspace"
Step 2: "I'll use stack to build final strings"
Step 3: "Then compare the results"

Key Points to Mention:
- Stack naturally handles backspace (pop)
- Build final string for each input
- Compare final strings
- Alternative: Two pointers O(1) space
- Process backwards to avoid building

Walk Through Example:
"For s='ab#c', t='ad#c':
 s: 'a','b','#','c'
    Push a, push b, pop b, push c → 'ac'
 t: 'a','d','#','c'
    Push a, push d, pop d, push c → 'ac'
 Compare: 'ac' == 'ac' → true"

Why Stack:
"Backspace deletes most recent character.
 Stack's pop() naturally removes most recent.
 Perfect match for the problem!"

Follow-up (O(1) space):
"Can process backwards using two pointers.
 Going right-to-left, backspace affects left.
 Skip characters based on backspace count.
 Compare valid characters without building."

Edge Cases to Mention:
✓ Empty result (all backspaced)
✓ More backspaces than characters
✓ No backspaces
✓ Different lengths

📝 Quick Revision Notes

🎯 Core Concept:

Backspace String Compare: Use stack to build final string. Regular char → push. '#' → pop (if not empty). Compare built strings. O(1) space: Two pointers from right to left, count backspaces, skip chars, compare valid chars without building.

⚡ Quick Implementation (Stack):

public boolean backspaceCompare(String s, String t) {
    return build(s).equals(build(t));
}

private String build(String str) {
    Stack<Character> stack = new Stack<>();
    for (char c : str.toCharArray()) {
        if (c == '#') {
            if (!stack.isEmpty()) stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.toString();
}

⚡ Optimal Implementation (Two Pointers):

class Solution {
  public boolean backspaceCompare(String s, String t) {
    // // Approach 1 - using stack
    // Stack<Character> stack1 = new Stack<>();
    // for(char c : s.toCharArray()) {
    //   if(c == '#') {
    //     if(!stack1.isEmpty()) {
    //       stack1.pop();
    //     }        
    //   } else {
    //     stack1.push(c);
    //   }
    // }

    // Stack<Character> stack2 = new Stack<>();
    // for(char c : t.toCharArray()) {      
    //   if(c == '#') {
    //     if(!stack2.isEmpty()) {
    //       stack2.pop();
    //     }
    //   } else {
    //     stack2.push(c);
    //   }
    // }

    // while (!stack1.isEmpty() && !stack2.isEmpty()) {
    //   if(stack1.pop() != stack2.pop()) {
    //     return false;
    //   }
    // }

    // return stack1.isEmpty() && stack2.isEmpty();

    // Approach 2 - using 2 pointers (space optimized)
    // key point - compare from back. skip number of # characters.
    int i = s.length() - 1;
    int j = t.length() - 1;

    while (i >= 0 || j >= 0) {
      i = getNextValidIndex(s, i);
      j = getNextValidIndex(t, j);

      // Done with both strings.
      if(i < 0 && j < 0) {
        return true;
      }

      // Still one is remaining while other is done. Its unequal now.
      if(i < 0 || j < 0) {
        return false;
      }

      if(s.charAt(i) != t.charAt(j)) {
        return false;
      }

      i--;
      j--;
    }

    return true;
  }

  private int getNextValidIndex(String s, int i) {
    int count = 0; // number of backspaces
    while (i >= 0) {      
      if(s.charAt(i) == '#') {
        // count the number of backspaces here.
        count++;
        i--;
      } else if(count > 0) {
        // if at the present character, still backspace count is there, ignore the current character.
        count--;
        i--;
      } else {
        break;
      }
    }

    return i;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.backspaceCompare("ab#c", "ad#c"));
    System.out.println(s.backspaceCompare("ab##", "c#d#"));
    System.out.println(s.backspaceCompare("a#c", "b"));
    System.out.println(s.backspaceCompare("a##c", "#a#c"));
    System.out.println(s.backspaceCompare("y#fo##f", "y#f#o##f"));
  }
}

🔑 Key Insights:

Pattern: Stack Pattern 2 (String Processing)
Stack: Push char, pop on '#'
Check empty: Before popping
Two pointers: Process backward for O(1)
Backward: Skip chars based on '#' count
Time: O(n+m), Space: O(n+m) or O(1) ✓

🎪 Memory Aid:

"Type pushes, backspace pops, then compare!"
"Push char, pop #, compare result!" ✨

⚠️ Critical Check:

ALWAYS check before pop:

❌ WRONG:
if (c == '#') {
    stack.pop();  // Crashes if empty!
}

✓ CORRECT:
if (c == '#') {
    if (!stack.isEmpty()) {
        stack.pop();
    }
}

Empty text + backspace = still empty!

🧪 Edge Cases

Case 1: All backspaced

Input: s = "ab##", t = "c#d#"
Output: true
Both become ""

Case 2: More backspaces than chars

Input: s = "a###a", t = "a"
Output: true
s: 'a', ###, 'a' → "a"
Extra backspaces do nothing

Case 3: No backspaces

Input: s = "abc", t = "abc"
Output: true
Direct comparison

Case 4: Different lengths

Input: s = "a#c", t = "b"
Output: false
s → "c", t → "b"

All handled correctly! ✓

Same Pattern: - Remove All Adjacent Duplicates (LC 1047) - Similar stack usage - Make String Great (LC 1544) - Remove adjacent case differences - Removing Stars (LC 2390) - Star removes left char

Two Pointers: - Valid Palindrome (LC 125) - Two pointers comparison

Happy practicing! 🎯

Note: This problem teaches Stack Pattern 2: String Processing! Master this and you understand: (1) character-by-character processing, (2) stack for undo/delete, (3) building final result, (4) O(1) space optimization with two pointers. The backward processing insight is brilliant - it's asked at Meta and Google! 💪✨

103. Backspace String Compare

Problem Statement

🌟 ELI5: The Simple Idea!

🎨 Visual Understanding

Example 1: Equal Strings

Example 2: Both Become Empty

🎯 Approach 1: Stack ⭐

The Intuitive Solution

Implementation

Alternative: Using StringBuilder

🎯 Approach 2: Two Pointers (O(1) Space) ⭐⭐

The Optimal Solution

Implementation

🔍 Super Detailed Dry Run (Two Pointers)

🎯 Why Two Pointers Works

The Right-to-Left Insight

The Backspace Logic

⚠️ Common Mistakes

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

📚 Related Problems