LeetCode Problem 844

Difficulty: 🟢 Easy
Topics: Two Pointers, String, Stack, Simulation

Solution

LeetCode 844 - Backspace String Compare

Problem Understanding

This problem asks us to determine whether two strings become identical after processing backspace operations. Each string represents characters typed into a text editor, where the '#' character means "delete the previous character", similar to pressing the backspace key on a keyboard.

We are given two input strings, s and t. Both strings contain lowercase English letters and the '#' character. We must simulate how each string would look after all typing and backspacing operations are completed, then compare the final results.

For example, if we process the string "ab#c":

• Type 'a' → "a"
• Type 'b' → "ab"
• '#' removes 'b' → "a"
• Type 'c' → "ac"

The final processed string is "ac".

The constraints are relatively small, with both strings having length at most 200. Because of this, even straightforward simulation approaches are fast enough. However, the follow-up question asks whether we can solve the problem in O(n) time and O(1) extra space, which encourages a more optimized solution.

Several edge cases are important:

• Multiple consecutive backspaces, such as "a###"
• Backspaces applied to an empty string, such as "###"
• Strings that become empty after processing
• Different raw strings producing identical final strings
• Strings of different lengths after processing

A naive implementation can easily fail if it tries to remove characters from an empty structure without checking first.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly build the final processed version of each string.

We can simulate typing using a stack:

• When we encounter a normal character, push it onto the stack.
• When we encounter '#', pop the top character if the stack is not empty.

After processing the entire string, the stack contains the final text editor state.

We repeat this process for both strings and compare the resulting strings.

This approach is correct because the stack naturally models the behavior of a text editor. The most recently typed character is the first one removed by a backspace operation.

Although this solution is efficient enough for the given constraints, it requires additional space proportional to the length of the strings.

Optimal Two Pointer Approach

The key observation is that we do not actually need to construct the final processed strings.

Instead, we can process both strings from right to left. When traversing backward:

• A '#' means we should skip one future character.
• Multiple '#' characters accumulate multiple skips.

This allows us to determine the next valid character in each string without building intermediate results.

Using two pointers:

• Start from the end of each string.
• Move backward while accounting for backspaces.
• Compare the next valid characters.
• If they differ, return False.
• If both strings finish simultaneously, return True.

This approach achieves O(1) extra space because we only use pointers and counters.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(n + m)	Simulates typing using stacks
Optimal	O(n + m)	O(1)	Uses backward traversal with two pointers

Algorithm Walkthrough

Optimal Two Pointer Algorithm

1. Initialize two pointers, one at the end of s and one at the end of t.
2. Create a helper process for each string that finds the next valid character by skipping deleted characters.
3. While processing a string backward:

• If the current character is '#', increment a skip counter and move left.
• If the current character is a letter and the skip counter is greater than zero, decrement the skip counter and move left.
• Otherwise, the current character is valid and ready for comparison.

4. After finding the next valid character in both strings:

• If only one string still has a valid character, return False.
• If both characters exist but are different, return False.

5. Move both pointers one step left and repeat the process.
6. If both strings are fully processed without mismatches, return True.

Why it works

The algorithm works because traversing backward lets us immediately determine whether a character survives all future backspaces. Every '#' cancels one preceding character. By maintaining a skip counter, we correctly ignore deleted characters without explicitly constructing the final string. Since each character is processed at most once, the comparison accurately matches the true final editor states.

Python Solution

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

        while i >= 0 or j >= 0:
            skip_s = 0
            while i >= 0:
                if s[i] == '#':
                    skip_s += 1
                    i -= 1
                elif skip_s > 0:
                    skip_s -= 1
                    i -= 1
                else:
                    break

            skip_t = 0
            while j >= 0:
                if t[j] == '#':
                    skip_t += 1
                    j -= 1
                elif skip_t > 0:
                    skip_t -= 1
                    j -= 1
                else:
                    break

            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i >= 0 or j >= 0:
                return False

            i -= 1
            j -= 1

        return True

The implementation starts by placing two pointers at the ends of the input strings. The main loop continues as long as at least one string still contains unprocessed characters.

Inside the loop, each string is processed independently to locate the next valid character. The skip_s and skip_t counters track how many characters should be ignored due to backspaces.

When a '#' is encountered, the skip counter increases. When a normal character appears while the skip counter is positive, that character is skipped because it has been deleted by a backspace.

Once valid characters are found in both strings, the algorithm compares them. If they differ, the strings cannot be equal after processing.

If one string still has characters remaining while the other does not, the final processed strings are different, so the function returns False.

If the loop finishes without mismatches, the processed strings are identical, so the function returns True.

Go Solution

func backspaceCompare(s string, t string) bool {
	i := len(s) - 1
	j := len(t) - 1

	for i >= 0 || j >= 0 {
		skipS := 0
		for i >= 0 {
			if s[i] == '#' {
				skipS++
				i--
			} else if skipS > 0 {
				skipS--
				i--
			} else {
				break
			}
		}

		skipT := 0
		for j >= 0 {
			if t[j] == '#' {
				skipT++
				j--
			} else if skipT > 0 {
				skipT--
				j--
			} else {
				break
			}
		}

		if i >= 0 && j >= 0 {
			if s[i] != t[j] {
				return false
			}
		} else if i >= 0 || j >= 0 {
			return false
		}

		i--
		j--
	}

	return true
}

The Go implementation follows the same logic as the Python version. Since Go strings are byte slices internally, indexing with s[i] directly accesses individual characters efficiently.

No special handling for nil is required because the problem guarantees valid string inputs. The algorithm uses integer indices and constant extra memory, matching the optimal complexity requirements.

Worked Examples

Example 1

Input

s = "ab#c"
t = "ad#c"

Step-by-step Trace

Step	i	j	s[i]	t[j]	Action
1	3	3	c	c	Compare equal
2	2	2	#	#	Skip previous chars
3	0	0	a	a	Compare equal
4	-1	-1	-	-	Finished

Final result: True

Both strings become "ac".

Example 2

Input

s = "ab##"
t = "c#d#"

Step-by-step Trace

Step	Action
Process s	a → ab → a → ""
Process t	c → "" → d → ""

Both final strings are empty.

Final result: True

Example 3

Input

s = "a#c"
t = "b"

Step-by-step Trace

Step	i	j	Valid Character in s	Valid Character in t
1	2	0	c	b

Since 'c' != 'b', the strings are different.

Final result: False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each character in both strings is processed at most once
Space	O(1)	Only pointers and counters are used

The algorithm achieves linear time because every character is visited at most one time during backward traversal. Even though nested loops appear in the implementation, the pointers only move left and never revisit characters.

The space complexity is constant because no auxiliary data structures proportional to input size are allocated.

Test Cases

solution = Solution()

assert solution.backspaceCompare("ab#c", "ad#c") == True   # basic matching case
assert solution.backspaceCompare("ab##", "c#d#") == True   # both become empty
assert solution.backspaceCompare("a#c", "b") == False      # different final strings
assert solution.backspaceCompare("a##c", "#a#c") == True   # multiple backspaces
assert solution.backspaceCompare("######", "###") == True  # only backspaces
assert solution.backspaceCompare("bxj##tw", "bxo#j##tw") == True  # complex deletions
assert solution.backspaceCompare("nzp#o#g", "b#nzp#o#g") == True  # leading deletions
assert solution.backspaceCompare("abc#d", "acc#c") == False       # mismatch after processing
assert solution.backspaceCompare("", "") == True                   # empty strings
assert solution.backspaceCompare("####a", "a") == True             # backspaces before character
assert solution.backspaceCompare("abc###", "") == True             # fully deleted string
assert solution.backspaceCompare("xywrrmp", "xywrrmu#p") == True   # deletion near end

Test	Why
"ab#c" vs "ad#c"	Standard matching example
"ab##" vs "c#d#"	Both strings become empty
"a#c" vs "b"	Different final results
"a##c" vs "#a#c"	Consecutive backspaces
"######" vs "###"	Only backspace characters
"bxj##tw" vs "bxo#j##tw"	Complex skip behavior
"nzp#o#g" vs "b#nzp#o#g"	Leading backspaces
"abc#d" vs "acc#c"	Character mismatch
"" vs ""	Empty input handling
"####a" vs "a"	Backspaces on empty text
"abc###" vs ""	Entire string deleted
"xywrrmp" vs "xywrrmu#p"	Backspace near end of string

Edge Cases

Consecutive Backspaces

Inputs like "a###" can easily cause bugs because there are more backspaces than actual characters. A naive implementation might attempt to remove characters from an empty stack or invalid index positions.

The two pointer solution handles this naturally using skip counters. Extra backspaces simply increase the skip count, and no invalid operations occur.

Strings That Become Empty

Cases such as "ab##" or "###" produce empty final strings. Some implementations incorrectly compare intermediate states instead of the fully processed results.

This implementation continues processing until both pointers are exhausted, ensuring empty final strings are compared correctly.

Unequal Remaining Characters

A subtle bug can occur when one processed string still contains valid characters while the other is already exhausted.

For example:

s = "a"
t = ""

After processing, one pointer remains valid while the other does not. The implementation explicitly checks this condition:

elif i >= 0 or j >= 0:
    return False

This guarantees correct behavior when processed string lengths differ.