Backspace String Compare

LeetCode 844: Backspace String Compare Solution & Explanation

Problem Overview

TL;DR: The optimal solution iterates backwards through both strings using two pointers to simulate the backspace logic on the fly, allowing for character comparison without allocating extra memory.

The LeetCode 844 problem, titled Backspace String Compare, asks us to determine if two given strings, s and t, are equivalent after processing backspace characters. In this context, the # symbol represents a backspace, meaning the character immediately preceding it is removed. If a backspace occurs when the text editor is empty, it remains empty. This is a popular interview question because it tests the ability to optimize space complexity beyond the obvious simulation approach.

Brute Force Approach for Backspace String Compare

The most intuitive way to solve this problem is to simulate the typing process exactly as described. We can build the final version of both strings by iterating through them from left to right. We use a stack (or a dynamic string builder) to store the characters. When we encounter a regular character, we push it onto the stack. When we encounter a #, we pop the top character from the stack if one exists.

After processing both strings completely, we compare the resulting stacks. If they are identical, the strings are equal.

Pseudo-code

function buildString(str):
    stack = empty
    for char in str:
        if char is '#':
            if stack is not empty:
                pop from stack
        else:
            push char to stack
    return stack as string

return buildString(s) == buildString(t)

Complexity Analysis

• Time Complexity: $O(N + M)$, where $N$ and $M$ are the lengths of strings s and t. We traverse each string once.
• Space Complexity: $O(N + M)$. In the worst case (e.g., no backspaces), we store all characters from both strings in memory.

Why It Fails

While this approach produces the correct result and passes basic time limits, it fails to meet the stricter constraints often imposed in senior-level interviews. Specifically, the problem includes a follow-up asking for a solution using $O(1)$ space. The brute force method requires linear space to reconstruct the strings, making it suboptimal for memory-constrained environments.

Algorithm Strategy: Two Pointer Patterns

1. Initialize Pointers: Set two pointers, i and j, to the last indices of string s and string t, respectively.
2. Outer Loop: Continue processing as long as either i or j is valid (greater than or equal to 0).
3. Find Next Valid Character in s:
   • Iterate backwards with i.
   • If s[i] is #, increment a skipS counter.
   • If s[i] is a letter and skipS > 0, decrement skipS (consuming a backspace) and ignore the character.
   • If s[i] is a letter and skipS == 0, stop. This is the next character to compare.
4. Find Next Valid Character in t:
   • Perform the exact same logic with pointer j and counter skipT to find the next valid character in t.
5. Compare:
   • If both i and j point to valid characters, check if s[i] == t[j]. If they differ, return false.
   • If one pointer is valid and the other has finished (index < 0), the strings have different lengths of valid characters. Return false.
6. Advance: Decrement both i and j to process the next set of characters.
7. Result: If the loop completes without returning false, the strings are equivalent. Return true.

Execution Flow

Let's trace s = "ab#c", t = "ad#c".

1. Start: i points to 'c' (index 3), j points to 'c' (index 3).
2. Find Valid s:
   • s[3] is 'c'. Not '#', skip count is 0. Valid char found: 'c'.
3. Find Valid t:
   • t[3] is 'c'. Not '#', skip count is 0. Valid char found: 'c'.
4. Compare: 'c' == 'c'. Match. Decrement i to 2, j to 2.
5. Find Valid s:
   • s[2] is '#'. Increment skipS to 1. Decrement i to 1.
   • s[1] is 'b'. Not '#', but skipS is 1. Decrement skipS to 0. Ignore 'b'. Decrement i to 0.
   • s[0] is 'a'. Not '#', skipS is 0. Valid char found: 'a'.
6. Find Valid t:
   • t[2] is '#'. Increment skipT to 1. Decrement j to 1.
   • t[1] is 'd'. Not '#', but skipT is 1. Decrement skipT to 0. Ignore 'd'. Decrement j to 0.
   • t[0] is 'a'. Not '#', skipT is 0. Valid char found: 'a'.
7. Compare: 'a' == 'a'. Match. Decrement i to -1, j to -1.
8. Loop End: Both indices are -1. Return true.

Proof of Correctness

The correctness relies on the invariant that iterating backwards allows us to resolve the effect of backspaces locally without needing future information. Since a backspace only affects characters to its left, a reverse scan encounters the operator (#) before the operand (the character to be deleted). By maintaining a counter of "unresolved backspaces," we ensure that every non-backspace character we stop at is part of the final string. Because we compare these valid characters one-by-one from the end, structural equality is rigorously checked. If at any point the characters mismatch or one string runs out of characters before the other, the strings cannot be equal.

Pattern Reuse Notes

The Two Pointers - String Comparison with Backspaces pattern and the concept of "effective depth" or "net movement" appear in similar simulation problems:

• LeetCode 1598: Crawler Log Folder: Instead of backspacing characters, you are navigating directories. ../ acts exactly like # (backspace), and ./ is a no-op. The logic of resolving the "net" path or depth uses a very similar state-tracking approach.

Reference Implementation

C++ Solution for LeetCode 844

1class Solution {
2public:
3    bool backspaceCompare(string s, string t) {
4        int i = s.length() - 1;
5        int j = t.length() - 1;
6        int skipS = 0;
7        int skipT = 0;
8
9        while (i >= 0 || j >= 0) {
10            // Find next valid char in s
11            while (i >= 0) {
12                if (s[i] == '#') {
13                    skipS++;
14                    i--;
15                } else if (skipS > 0) {
16                    skipS--;
17                    i--;
18                } else {
19                    break; // Found a valid character
20                }
21            }
22
23            // Find next valid char in t
24            while (j >= 0) {
25                if (t[j] == '#') {
26                    skipT++;
27                    j--;
28                } else if (skipT > 0) {
29                    skipT--;
30                    j--;
31                } else {
32                    break; // Found a valid character
33                }
34            }
35
36            // Compare characters
37            // If both are valid indices, chars must match
38            if (i >= 0 && j >= 0) {
39                if (s[i] != t[j]) return false;
40            }
41            // If one is valid and the other is not
42            else if (i >= 0 || j >= 0) {
43                return false;
44            }
45
46            // Move to next char
47            i--;
48            j--;
49        }
50
51        return true;
52    }
53};

Java Solution for LeetCode 844

1class Solution {
2    public boolean backspaceCompare(String s, String t) {
3        int i = s.length() - 1;
4        int j = t.length() - 1;
5        int skipS = 0;
6        int skipT = 0;
7
8        while (i >= 0 || j >= 0) {
9            // Find next valid char in s
10            while (i >= 0) {
11                if (s.charAt(i) == '#') {
12                    skipS++;
13                    i--;
14                } else if (skipS > 0) {
15                    skipS--;
16                    i--;
17                } else {
18                    break;
19                }
20            }
21
22            // Find next valid char in t
23            while (j >= 0) {
24                if (t.charAt(j) == '#') {
25                    skipT++;
26                    j--;
27                } else if (skipT > 0) {
28                    skipT--;
29                    j--;
30                } else {
31                    break;
32                }
33            }
34
35            // If both valid, compare
36            if (i >= 0 && j >= 0) {
37                if (s.charAt(i) != t.charAt(j)) {
38                    return false;
39                }
40            }
41            // If one finished but other didn't
42            else if (i >= 0 || j >= 0) {
43                return false;
44            }
45
46            i--;
47            j--;
48        }
49
50        return true;
51    }
52}

Python Solution for LeetCode 844

1class Solution:
2    def backspaceCompare(self, s: str, t: str) -> bool:
3        i, j = len(s) - 1, len(t) - 1
4        skip_s, skip_t = 0, 0
5
6        while i >= 0 or j >= 0:
7            # Find next valid char in s
8            while i >= 0:
9                if s[i] == '#':
10                    skip_s += 1
11                    i -= 1
12                elif skip_s > 0:
13                    skip_s -= 1
14                    i -= 1
15                else:
16                    break
17            
18            # Find next valid char in t
19            while j >= 0:
20                if t[j] == '#':
21                    skip_t += 1
22                    j -= 1
23                elif skip_t > 0:
24                    skip_t -= 1
25                    j -= 1
26                else:
27                    break
28            
29            # Compare characters
30            if i >= 0 and j >= 0:
31                if s[i] != t[j]:
32                    return false
33            elif i >= 0 or j >= 0:
34                # One string is exhausted, the other is not
35                return False
36            
37            i -= 1
38            j -= 1
39            
40        return True