Loading problems...
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.
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.
textfunction 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)
s and t. We traverse each string once.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 space. The brute force method requires linear space to reconstruct the strings, making it suboptimal for memory-constrained environments.
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:
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.

Let's trace s = "ab#c", t = "ad#c".
i points to 'c' (index 3), j points to 'c' (index 3).s:
s[3] is 'c'. Not '#', skip count is 0. Valid char found: 'c'.t:
t[3] is 'c'. Not '#', skip count is 0. Valid char found: 'c'.i to 2, j to 2.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'.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'.i to -1, j to -1.true.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.
cppclass 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; } };
javaclass 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; } }
pythonclass 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
Time Complexity:
We traverse each character in string s and string t at most once. Although there are nested loops (to find the next valid character), the pointers i and j only decrement and never reset. Thus, the total operations are linear relative to the string lengths.
Space Complexity:
We only use a few integer variables (i, j, skipS, skipT) to maintain state. We do not allocate any new strings, stacks, or arrays, satisfying the follow-up constraint.
The Two Pointers - String Comparison with Backspaces pattern and the concept of "effective depth" or "net movement" appear in similar simulation problems:
../ 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.Q: Why does my solution fail when one string is empty after processing?
Mistake: Failing to check if one pointer drops below 0 while the other remains valid.
Why: It is possible for one string to reduce to an empty string (e.g., ab##) while the other still has characters (e.g., c).
Consequence: The logic might attempt to access s[-1] or erroneously return true because it didn't strictly validate that both strings must be exhausted simultaneously.
Q: Why does my loop logic get complicated?
Mistake: Attempting to handle the # skipping and the comparison in the same if/else block without nested loops.
Why: A single character position might require skipping multiple backspaces (e.g., abc###). The logic to "find the next valid character" is repetitive and best handled by a dedicated inner loop.
Consequence: Code becomes spaghetti-like and prone to bugs where backspaces are not fully resolved before comparison.
Q: Why is my space complexity still ?
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 space, even if the logic is otherwise correct.