How do you solve Backspace String Compare?

Use two pointers starting at the end of s and t. Define a helper function that moves the pointer backwards, skipping characters removed by backspaces using a skip counter. At each step, retrieve the next valid character from both strings and compare. If any mismatch occurs, return false. If both pointers reach the beginning, return true.

What pattern does Backspace String Compare use?

The Pattern: Two Pointers (Greedy Backward Traversal) The Heuristic: When simulating string transformations with deletions like backspaces, iterating from the end with skip counters allows skipping invalid characters on the fly, enabling O(1) space comparison without reconstructing strings.

Backspace String Compare — Two Pointers

Q: What is the time complexity of Backspace String Compare?

O(n + m). Each pointer traverses its string at most once, skipping characters as needed, resulting in linear time proportional to the sum of the input lengths.

Problem

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

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

Example

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

Output: true

Both strings become "ac" after processing backspaces. The algorithm simulates typing from the end, skipping characters that are removed by backspaces. For s, starting from the end: 'c' is valid, then '#' removes 'b', leaving 'a'. For t, similarly, 'c' is valid, '#' removes 'd', leaving 'a'. Since both processed strings are equal, the output is true.

Approach

Straightforward Solution

A brute-force approach builds the final strings by simulating the typing process with a stack or string builder, then compares the results. This uses O(n) extra space and two passes.

Core Observation

Backspace characters remove the immediately preceding character if any. Processing from the end allows skipping characters efficiently without reconstructing the entire string.

Path to Optimal

Preview

The key insight is that the problem can be solved in O(n) time and O(1) space by iterating backwards with two pointers and a skip counter…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers starting at the end of s and t. Define a helper function that moves the pointer backwards, skipping characters removed by backspaces using a skip counter…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Each pointer traverses its string at most once, skipping characters as needed, resulting in linear time proportional to the sum of the input lengths.

Space

O(1)

Only a fixed number of variables (pointers and counters) are used, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
  def backspaceCompare(self, s: str, t: str) -> bool:
      def next_char(string, i):
          skip = 0
          while i >= 0:
              if string[i] == '#':
                  skip += 1
              elif skip > 0:
                  skip -= 1
              else:
                  return string[i], i - 1
              i -= 1
          return None, i
      
      i, j = len(s) - 1, len(t) - 1
      
      while i >= 0 or j >= 0:
          c1, i = next_char(s, i)
          c2, j = next_char(t, j)
          if c1 != c2:
              return False
      return True

Step-by-Step Solution

1

Implement Helper to Find Next Valid Character in a String

3def next_char(string, i):
  skip = 0
  while i >= 0:
      if string[i] == '#':
          skip += 1
      elif skip > 0:
          skip -= 1
      else:
          return string[i], i - 1
      i -= 1
  return None, i

Objective

To locate the next character in the string that is not removed by backspaces by iterating backwards and managing a skip counter.

Key Insight

By moving backwards and incrementing skip when encountering '#', the algorithm knows how many characters to skip. When a non-backspace character is found, if skip is positive, it is skipped and skip is decremented. Otherwise, this character is valid and returned. This approach avoids building the final string and handles consecutive backspaces efficiently.

Interview Quick-Check

Core Logic

The helper function uses a skip counter to track how many characters to ignore due to backspaces, iterating backwards until it finds a valid character or exhausts the string.

State & Boundaries

The function returns None and the updated index when no valid character remains, signaling the end of the string.

Common Pitfalls & Bugs

A common mistake is not decrementing the pointer correctly after skipping characters, which can cause infinite loops or incorrect results.

2

Compare Both Strings Using Two Pointers and Helper

To iterate through both strings from the end, comparing their next valid characters until a mismatch is found or both strings are fully processed.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 10 Critical

else:

Return current character and updated index if it is valid (not skipped).

This return is the critical step that outputs the next valid character after accounting for backspaces, enabling the two-pointer comparison without extra space.

Line 20 Critical

if c1 != c2:

Compare the two characters; if they differ, return False.

This comparison is the decisive check that determines if the processed strings are equal; any mismatch invalidates equality immediately.

Line 22 Critical

return True

Return True if all characters matched and both strings are fully processed.

Returning True here confirms that all characters matched in order, proving the strings are equivalent after applying backspaces.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does iterating from the end with a skip counter correctly simulate the effect of backspaces without reconstructing the entire string?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Backspace String Compare from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Backspace String Compare drill

or drill a free problem

1	`class Solution:`
2	`def backspaceCompare(self, s: str, t: str) -> bool:`
3	`def next_char(string, i):`
4	`skip = 0`
5	`while i >= 0:`
6	`if string[i] == '#':`
7	`skip += 1`
8	`elif skip > 0:`
9	`skip -= 1`
10	`else:`
11	`return string[i], i - 1`
12	`i -= 1`
13	`return None, i`
14
15	`i, j = len(s) - 1, len(t) - 1`
16
17	`while i >= 0 or j >= 0:`
18	`c1, i = next_char(s, i)`
19	`c2, j = next_char(t, j)`
20	`if c1 != c2:`
21	`return False`
22	`return True`

3	`def next_char(string, i):`
4	`skip = 0`
5	`while i >= 0:`
6	`if string[i] == '#':`
7	`skip += 1`
8	`elif skip > 0:`
9	`skip -= 1`
10	`else:`
11	`return string[i], i - 1`
12	`i -= 1`
13	`return None, i`