844. Backspace String Compare - Explanation

1. Stack

Intuition

The backspace character # removes the previous character, which is exactly what a stack does well. We can simulate typing each string by pushing regular characters onto a stack and popping when we see a #. After processing both strings this way, we just compare the resulting stacks.

Algorithm

Create a helper function that converts a string to its final form using a stack.
For each character in the string:
- If it's # and the stack is not empty, pop from the stack.
- Otherwise, push the character onto the stack.
Convert the stack to a string.
Compare the converted versions of both input strings.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def convert(s):
            res = []
            for char in s:
                if char == '#':
                    if res:
                        res.pop()
                else:
                    res.append(char)
            return "".join(res)

        return convert(s) == convert(t)

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

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

2. Reverse iteration

Intuition

Instead of building the result from the beginning, we can iterate from the end. When we encounter a #, we know we need to skip the next valid character. By counting backspaces as we go backward, we can skip the right number of characters before adding one to our result. This still uses extra space for storing the result, but gives us a different perspective on the problem.

Algorithm

Create a helper function that processes a string from right to left.
Start from the last character and maintain a backspace counter.
For each character going backward:
- If it's #, increment the backspace count.
- Else if the backspace count is positive, decrement it (skip this character).
- Otherwise, add the character to the result.
Compare the processed versions of both strings.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def convert(s):
            res = []
            backspace = 0
            for i in range(len(s) - 1, -1, -1):
                if s[i] == '#':
                    backspace += 1
                elif backspace:
                    backspace -= 1
                else:
                    res.append(s[i])
            return res

        return convert(s) == convert(t)

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n + m)$

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

3. Two Pointers - I

Intuition

We can compare the strings character by character without building the full result. Starting from the end of both strings, we find the next valid character in each (skipping over characters deleted by backspaces). If at any point these characters differ, the strings are not equal. This approach uses O(1) extra space since we only track pointers and counts.

Algorithm

Initialize two pointers at the end of each string.
Create a helper function that finds the next valid character index by:
- Counting backspaces encountered.
- Skipping characters that would be deleted.
- Returning the index of the next valid character (or -1 if none).
While either pointer is valid:
- Find the next valid character in each string.
- Compare them (treat out-of-bounds as empty).
- If they differ, return false.
- Move both pointers left.
Return true if we finish without finding a mismatch.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def nextValidChar(string, index):
            backspace = 0
            while index >= 0:
                if string[index] == '#':
                    backspace += 1
                elif backspace > 0:
                    backspace -= 1
                else:
                    break
                index -= 1
            return index

        index_s, index_t = len(s) - 1, len(t) - 1

        while index_s >= 0 or index_t >= 0:
            index_s = nextValidChar(s, index_s)
            index_t = nextValidChar(t, index_t)

            char_s = s[index_s] if index_s >= 0 else ""
            char_t = t[index_t] if index_t >= 0 else ""

            if char_s != char_t:
                return False

            index_s -= 1
            index_t -= 1

        return True

Time & Space 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$ .

4. Two Pointers - II

Intuition

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.

Algorithm

Initialize pointers at the end of both strings and backspace counters for each.
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.
Return true if all comparisons passed.

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

Time & Space 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$ .

Common Pitfalls

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.

# Wrong: unconditional pop
if char == '#':
    stack.pop()
# Right: check before popping
if char == '#':
    if stack:
        stack.pop()

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.

# Wrong: left-to-right doesn't work for O(1) space
for i in range(len(s)):  # can't determine final result this way
# Right: right-to-left with backspace counting
for i in range(len(s) - 1, -1, -1):