#844

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Backspace String Compare

Compare two strings after processing backspaces using efficient two-pointer scanning and careful invariant tracking to ensure correctness.

two pointers string stack simulation

Problem Statement

Given two strings s and t, each containing lowercase letters and '#' characters representing backspaces, determine whether they are equal when typed into empty text editors. A backspace '#' deletes the previous character if any; if the text is empty, it has no effect.

For example, with s = "ab#c" and t = "ad#c", both become "ac" after processing, so the output is true. Implement an algorithm that efficiently handles strings up to length 200 and returns a boolean indicating equality after backspaces.

Examples

Example 1

Input: s = "ab#c", t = "ad#c"

Output: true

Both s and t become "ac".

Example 2

Input: s = "ab##", t = "c#d#"

Output: true

Both s and t become "".

Example 3

Input: s = "a#c", t = "b"

Output: false

s becomes "c" while t becomes "b".

Constraints

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.

Solution Approach

Two-pointer backward scan

Start from the end of both strings with two pointers. Track skip counts for each string to ignore characters deleted by backspaces. Move pointers backward until the next valid character and compare them at each step.

Invariant character comparison

Maintain the invariant that each pointer points to a valid character not removed by backspaces. Compare these valid characters immediately. If any mismatch occurs, return false; otherwise, continue until both pointers reach the start.

Constant space optimization

Avoid building new strings or stacks. Only use counters to track pending backspaces. This reduces extra memory usage to O(1) while preserving linear time complexity O(M + N) over the lengths of the input strings.

Complexity Analysis

Metric	Value
Time	O(M + N)
Space	O(1)

Time complexity is O(M + N) since each character in s and t is processed at most once. Space complexity is O(1) because only counters and pointers are used without additional storage.

What Interviewers Usually Probe

Check if you can handle consecutive backspaces correctly when pointers cross multiple '#' characters.
Notice if the candidate compares characters without correctly skipping invalid ones.
Watch if they optimize space by avoiding auxiliary stacks or rebuilt strings.

Common Pitfalls or Variants

Common pitfalls

Failing to skip multiple consecutive backspaces properly leading to incorrect character comparisons.
Attempting to build processed strings instead of scanning with two pointers, increasing unnecessary space usage.
Not handling cases where one string is exhausted while the other still has pending backspaces.

Follow-up variants

Compare strings with different special characters representing backspaces or deletions.
Compute equality when backspaces are applied from the start instead of scanning backward.
Determine if one string can be transformed into the other using a limited number of backspaces.

FAQ

What is the best way to compare strings with backspaces in Backspace String Compare?

Use a two-pointer backward scan to handle backspaces without extra space, comparing valid characters as you move pointers.

Can I use a stack to solve this problem?

Yes, but it uses O(N) extra space. Two-pointer scanning is preferred to maintain O(1) space while keeping linear time.

How do I handle consecutive '#' characters?

Increment a skip counter for each '#' and decrement it when skipping valid characters until the counter is zero.

Does GhostInterview provide a ready-to-run solution?

It provides guided solutions with stepwise two-pointer reasoning and invariant tracking but encourages writing code based on the approach.

What are key failure points in this problem?

Not correctly skipping characters removed by multiple backspaces or misaligning pointers between the two strings often causes wrong answers.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0
        while i >= 0 or j >= 0:
            while i >= 0:
                if s[i] == '#':
                    skip1 += 1
                    i -= 1
                elif skip1:
                    skip1 -= 1
                    i -= 1
                else:
                    break
            while j >= 0:
                if t[j] == '#':
                    skip2 += 1
                    j -= 1
                elif skip2:
                    skip2 -= 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, j = i - 1, j - 1
        return True

Continue Practicing

#832 flipping an image #770 basic calculator iv #763 partition labels