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.

Thinking Process

  1. Backwards Processing: Processing from right to left handles backspaces naturally
  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Monotonic stack (this problem) O(n) O(n) Next greater/smaller element
Parentheses matching O(n) O(n) Push open, pop on close
Expression evaluation O(n) O(n) Operand + operator stacks
Stack simulation O(n) O(n) Process in LIFO order

Examples

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.

Alternative Approach: Stack-Based

class Solution {
        public boolean backspaceCompare(String s, String t) {
        // 1. String construct: ab#c backwards construct: ca
        // Request: O(n) time O(1) space . in space update.
        // 2. backwars, 2 pointers: if # move 2 backwards,  then compare
        int i = s.length() -1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while(i >= 0 || j >= 0) {
            while(i >) {
                if(s.charAt(i) == '#') {skipS++; i--;}
                else if(skipS > 0) {skipS--; i--;}
                else break;
            }
            while(j >) {
                if(t.charAt(j) == '#') {skipT++; j--;}
                else if(skipT > 0) {skipT--; j--;}
                else break;
            }
            if(i >= 0 && j>= 0 && s.charAt(i) != t.charAt(j)) return false;
            i--;
            j--;
        }
        return i == j;
    }
}

Time Complexity: O(n + m)
Space Complexity: O(n + m)

Comparison:

  • Stack-based: Simpler to understand, but uses O(n + m) space
  • Two Pointers: More complex, but O(1) space - better for large inputs

Common Mistakes

  1. All backspaces: s = "###", t = "##" → both become "", return true
  2. Empty strings: s = "", t = "" → return true
  3. Backspace at start: s = "#a", t = "a" → both become "a", return true
  4. Different lengths: s = "a#b", t = "b" → both become "b", return true

  5. No backspaces: s = "abc", t = "abc" → return true

  6. Wrong skip logic: Not properly handling consecutive backspaces
  7. Index errors: Off-by-one errors when moving pointers
  8. Missing break: Not breaking from inner loops when finding actual character
  9. Wrong comparison: Comparing before processing all backspaces
  10. Return condition: Not checking i == j correctly (both should be -1)

Key Takeaways

  1. Backwards Processing: Processing from right to left handles backspaces naturally
  2. Skip Counter: Tracks characters to skip due to backspaces
  3. Character Matching: Only compares actual characters after handling backspaces
  4. Space Efficiency: Two-pointer approach achieves O(1) space

References

Template Reference