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 - LeetCode Solution

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

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. Instead of building the final strings, the algorithm finds the next valid character in each string by skipping characters removed by backspaces. Comparing these characters step-by-step avoids extra space and reconstructing strings.

Optimal Approach

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.

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

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

15i, j = len(s) - 1, len(t) - 1
17while 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
22return True

Objective

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

Key Insight

By repeatedly calling the helper to get the next valid character from each string, the algorithm compares characters one by one. If characters differ, it returns false immediately. If both pointers reach the start without mismatches, the strings are equal after backspace processing. This approach efficiently compares without extra space or reconstructing strings.

Interview Quick-Check

Core Logic

The main loop uses the helper to get the next valid character from each string and compares them, returning false on mismatch and true if both strings are exhausted simultaneously.

State & Boundaries

The loop continues while either pointer is valid (>= 0), ensuring all characters are compared.

Common Pitfalls & Bugs

Failing to handle the case where one string is exhausted before the other leads to incorrect equality results.

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.

Line 8 Critical

elif skip > 0:

Check if skip counter is positive and current character is not '#'.

If skip is positive, the current character is removed by a previous backspace and should be skipped.

Line 9 Critical

skip -= 1

Decrement skip counter when skipping a character.

Decreasing skip ensures the correct number of characters are skipped, matching the number of backspaces encountered.

Line 18 Critical

c1, i = next_char(s, i)

Get next valid character and updated index from s using helper.

Retrieving the next valid character from s accounts for backspaces without reconstructing the string.

Line 19 Critical

c2, j = next_char(t, j)

Get next valid character and updated index from t using helper.

Similarly retrieves the next valid character from t, enabling synchronized comparison.

Line 5 Core

while i >= 0:

Start a loop to move backwards through the string while index is valid.

Iterating backwards is essential because backspaces remove preceding characters, so processing from the end allows skipping efficiently.

Line 6 Core

if string[i] == '#':

Check if current character is a backspace '#'.

Identifying backspaces increments the skip counter, indicating subsequent characters should be skipped.

Line 7 Core

skip += 1

Increment skip counter when encountering '#'.

Each '#' increases the number of characters to skip, reflecting the backspace effect.

Line 12 Core

i -= 1

Return None and index when no valid character remains.

Signaling the end of the string with None allows the main loop to detect when all characters have been processed.

Line 17 Core

while i >= 0 or j >= 0:

Loop while either pointer is valid (>= 0).

Ensures all characters in both strings are compared, including cases where strings differ in length after backspace processing.

Line 21 Core

return False

Return False immediately if characters differ.

Early termination improves efficiency by avoiding unnecessary further comparisons once inequality is detected.

Line 3 Core

def next_char(string, i):

Define helper function to find next valid character in a string from index i backwards.

Encapsulating the logic for skipping backspaced characters into a helper function isolates complexity and enables reuse for both strings.

Line 4 Core

skip = 0

Initialize skip counter to zero.

The skip counter tracks how many characters must be ignored due to backspaces, enabling correct skipping logic.

Line 11 Core

return string[i], i - 1

Move pointer one step backward.

Decrementing the index moves the scan backward through the string, essential for the reverse traversal logic.

Line 15 Core

i, j = len(s) - 1, len(t) - 1

Initialize pointers i and j at the end of strings s and t respectively.

Starting from the end aligns with the helper's backward traversal, enabling efficient skipping of backspaced characters.

Line 13 Basic

return None, i

End of helper function.

Completes the helper's logic for finding the next valid character.

Test Your Understanding

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

Because backspaces remove the closest preceding character, iterating backwards and counting skips allows the algorithm to ignore characters that would have been deleted, effectively simulating the final string from the end without extra space.

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`