text
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.

Core Insight for Backspace String Compare

The key intuition for the optimal LeetCode 844 solution lies in the direction of iteration.

If we iterate forward (left to right), we cannot know if a character will be deleted until we see the subsequent characters. For example, in abc##, we process a, then b, then c, and only then realize b and c are deleted.

However, if we iterate backwards (right to left), we encounter the backspace character # before the character it deletes. This allows us to maintain a count of "pending backspaces." When we see a #, we increment our skip counter. When we see a regular character, we check the skip counter:

1. If the counter is positive, we "spend" a backspace to delete the current character and continue moving left.
2. If the counter is zero, the current character is valid and part of the final string.

This reverse traversal guarantees that whenever we stop at a non-skip character, it is definitely a character that survives the editing process. We can then compare the valid characters of s and t directly.

Visual Description: Imagine two pointers, one at the end of s and one at the end of t. As they slide to the left, they act as "scanners." If a scanner hits a #, it charges up a "skip battery." As it continues left, it uses this battery charge to zap (ignore) regular letters. The scanners only pause to compare values when their batteries are empty and they are sitting on a regular letter.

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.

Reference Implementation

C++ Solution for LeetCode 844

cpp
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int skipS = 0;
        int skipT = 0;

        while (i >= 0 || j >= 0) {
            // Find next valid char in s
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break; // Found a valid character
                }
            }

            // Find next valid char in t
            while (j >= 0) {
                if (t[j] == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break; // Found a valid character
                }
            }

            // Compare characters
            // If both are valid indices, chars must match
            if (i >= 0 && j >= 0) {
                if (s[i] != t[j]) return false;
            }
            // If one is valid and the other is not
            else if (i >= 0 || j >= 0) {
                return false;
            }

            // Move to next char
            i--;
            j--;
        }

        return true;
    }
};

Java Solution for LeetCode 844

java
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int skipS = 0;
        int skipT = 0;

        while (i >= 0 || j >= 0) {
            // Find next valid char in s
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

            // Find next valid char in t
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            // If both valid, compare
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            }
            // If one finished but other didn't
            else if (i >= 0 || j >= 0) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
}

Python Solution for LeetCode 844

python
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        skip_s, skip_t = 0, 0

        while i >= 0 or j >= 0:
            # Find next valid char in s
            while i >= 0:
                if s[i] == '#':
                    skip_s += 1
                    i -= 1
                elif skip_s > 0:
                    skip_s -= 1
                    i -= 1
                else:
                    break
            
            # Find next valid char in t
            while j >= 0:
                if t[j] == '#':
                    skip_t += 1
                    j -= 1
                elif skip_t > 0:
                    skip_t -= 1
                    j -= 1
                else:
                    break
            
            # Compare characters
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return false
            elif i >= 0 or j >= 0:
                # One string is exhausted, the other is not
                return False
            
            i -= 1
            j -= 1
            
        return True

Q: Why is my space complexity still $O(N)$? Mistake: Using recursion or string.replace() or split(). Why: Recursion adds stack frames proportional to the string length. String manipulation methods often create new copies of the string. Consequence: You fail the specific interview constraint of $O(1)$ space, even if the logic is otherwise correct.