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:
    def backspaceCompare(self, s, t):
        i, j = len(s) - 1, len(t) - 1
        skipS, skipT = 0, 0

        while i >= 0 or j >= 0:

            # find next valid char in s
            while i >= 0:
                if s[i] == '#':
                    skipS += 1
                    i -= 1
                elif skipS > 0:
                    skipS -= 1
                    i -= 1
                else:
                    break

            # find next valid char in t
            while j >= 0:
                if t[j] == '#':
                    skipT += 1
                    j -= 1
                elif skipT > 0:
                    skipT -= 1
                    j -= 1
                else:
                    break

            # compare
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i >= 0 or j >= 0:
                return False

            i -= 1
            j -= 1

        return True

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