Backspace String Compare

Easy · Two Pointers · Explanation and code example

Two Pointers - II

How it works

This is a more compact version of the two-pointer approach. Instead of using a helper function, we inline the logic for skipping characters. The core idea remains the same: iterate backward through both strings simultaneously, skip characters that would be deleted by backspaces, and compare the remaining characters one by one.

Steps

  1. Initialize pointers at the end of both strings and backspace counters for each.
  2. Loop until both pointers are exhausted:
    • For each string, skip backward while there are backspaces to apply or # characters to count.
    • Compare the current valid characters from both strings.
    • If they don't match, check if both pointers are -1 (both exhausted). If not, return false.
    • Move both pointers left and continue.
  3. Return true if all comparisons passed.

Complexity

  • Time complexity: O(n + m)
  • Space complexity: O(1)

Where n is the length of the string s and m is the length of the string t.

Things to watch for

Popping from Empty Stack

When processing a backspace character, you must check if the stack is non-empty before popping, since backspaces at the start of a string have no effect.

Processing Strings Left-to-Right in Two-Pointer Approach

The O(1) space two-pointer solution must iterate from right to left. Going left to right makes it impossible to know how many characters will be deleted ahead of time.

Python code example

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        index_s, index_t = len(s) - 1, len(t) - 1
        backspace_s = backspace_t = 0

        while True:
            while index_s >= 0 and (backspace_s or s[index_s] == '#'):
                backspace_s += 1 if s[index_s] == '#' else -1
                index_s -= 1

            while index_t >= 0 and (backspace_t or t[index_t] == '#'):
                backspace_t += 1 if t[index_t] == '#' else -1
                index_t -= 1

            if not (index_s >= 0 and index_t >= 0 and s[index_s] == t[index_t]):
                return index_s == index_t == -1
            index_s, index_t = index_s - 1, index_t - 1

C++ code example

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int indexS = s.size() - 1, indexT = t.size() - 1;
        int backspaceS = 0, backspaceT = 0;

        while (true) {

            while (indexS >= 0 && (backspaceS > 0 || s[indexS] == '#')) {
                backspaceS += (s[indexS] == '#') ? 1 : -1;
                indexS--;
            }

            while (indexT >= 0 && (backspaceT > 0 || t[indexT] == '#')) {
                backspaceT += (t[indexT] == '#') ? 1 : -1;
                indexT--;
            }

            if (!(indexS >= 0 && indexT >= 0 && s[indexS] == t[indexT])) {
                return indexS == -1 && indexT == -1;
            }
            indexS--;
            indexT--;
        }
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations