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:
    bool backspaceCompare(string s, string t) {
        return buildString(s) == buildString(t);
    }
    
private:
    string buildString(string& str) {
        string result;
        for(char c : str) {
            if(c == '#') {
                if(!result.empty()) {
                    result.pop_back();
                }
            } else {
                result.push_back(c);
            }
        }
        return result;
    }
};

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