Understanding the Problem

We have two strings where the # character acts like a backspace key. When you encounter a #, it deletes the character immediately before it (if one exists). If the text is already empty, the backspace does nothing.

Our job is to figure out whether both strings produce the same final result after processing all the backspaces.

The simplest way to think about this: simulate what a text editor does. Process each string character by character, applying backspaces as you go, then compare the two results. But the follow-up asks us to do this without building the final strings at all, which pushes us toward a clever two-pointer approach that works backwards through both strings.

Key Constraints:

1 <= s.length, t.length <= 200 → With lengths at most 200, even an O(n^2) approach would be fast. But the follow-up challenges us to achieve O(n) time and O(1) space.
s and t only contain lowercase letters and '#' characters → No uppercase, no special characters beyond #. Simple character handling.

Approach 1: Build String with Stack

Intuition

The most natural way to think about this: simulate exactly what a text editor does. You read characters from left to right. If you see a regular letter, type it. If you see a #, press backspace (delete the last character you typed).

This is textbook stack behavior. Push letters onto the stack, and pop when you hit a #. After processing both strings, whatever remains in each stack is the final text. If they match, return true.

Algorithm

Create a helper function that takes a string and returns the "typed out" result:

Initialize an empty stack.
For each character in the string:

If it's a # and the stack isn't empty, pop the top element.
If it's a regular letter, push it onto the stack.

Convert the stack to a string and return it.

Apply this helper to both s and t.
Compare the two results. If they're equal, return true.

Example Walkthrough

1Start processing s = "ab#c"

1/5

1Stack empty, start processing s

1/5

Code

Complexity Analysis

Time Complexity: O(n + m). We process each character in s (length n) and t (length m) exactly once. Each stack operation is O(1), and the final string comparison is O(min(n, m)).
Space Complexity: O(n + m). We build result strings for both s and t, each up to the length of the original string.

This approach works correctly but uses O(n + m) extra space to store the built strings. What if we could compare the strings character by character without ever constructing them?

Approach 2: Two Pointers from the End (Optimal)

Intuition

Here's the key insight: backspaces only affect characters to their left. So if we process the strings from right to left, we can handle backspaces as we encounter them. When we see a #, we know some number of upcoming characters (moving leftward) need to be skipped. We keep a counter of how many characters to skip.

The approach works like this: start two pointers at the end of each string. For each string, walk left while skipping characters that have been "backspaced." Once both pointers land on a character that actually survives, compare them. If they differ, the strings aren't equal. If both pointers exhaust their strings at the same time, the strings are equal.

Why does this work?

The reason we can process backwards is that a # only ever affects characters to its left. When we walk from right to left, we encounter the # before the characters it would delete. So we simply count how many characters to skip and skip them as we continue leftward.

This is different from processing forward, where you don't know if the current character will be deleted by a future #. By going backwards, every # we see immediately tells us to skip one future (leftward) character. There's no ambiguity.

Algorithm

Initialize pointer i at the end of s and pointer j at the end of t.
Initialize skipS = 0 and skipT = 0 to count pending backspaces.
Loop while i >= 0 or j >= 0:

Advance pointer i leftward, processing backspaces for s:

If s[i] is #, increment skipS and move left.
Else if skipS > 0, decrement skipS (skip this character) and move left.
Otherwise, i is at a valid character. Stop.

Do the same for pointer j with string t.
Now compare:

If both i >= 0 and j >= 0: compare s[i] and t[j]. If they differ, return false.
If one pointer is valid and the other isn't: return false.

Decrement both i and j to move to the next characters.

If the loop finishes without returning false, return true.

Example Walkthrough

1Initialize: i=3, skipS=0. Start from end of s.

1/5

1Initialize: j=3, skipT=0. Start from end of t.

1/5

Code

Complexity Analysis

Time Complexity: O(n + m). Each character in both strings is visited at most twice: once when the pointer passes over it, and potentially once when it's skipped due to a backspace. Total work is linear in the combined length.
Space Complexity: O(1). Only a constant number of variables (i, j, skipS, skipT) regardless of input size.

Backspace String Compare

Understanding the Problem

Key Constraints:

Approach 1: Build String with Stack

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Two Pointers from the End (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium