Domain 1EasyCORE

Backspace String Compare

The problem requires us to compare two strings `s` and `t` after simulating the effect of backspace characters (`'#'`). The task is to determine if both strings are equal when typed into an empty text editor. A backspace character removes the last character from the string, unless the string is already empty.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Two Pointers#Stack

844. Backspace String Compare

Model: qwen2.5-coder:14b
Topics: Two Pointers,Stack
FAANG asked: 1
Acceptance rate: 47.2%


Problem Breakdown

The problem requires us to compare two strings s and t after simulating the effect of backspace characters ('#'). The task is to determine if both strings are equal when typed into an empty text editor. A backspace character removes the last character from the string, unless the string is already empty.

Inputs:

  • Two strings s and t, each containing lowercase letters and '#'.

Outputs:

  • A boolean value indicating whether the processed versions of s and t are equal.

Implicit Constraints:

  • The strings can be up to 200 characters long.
  • Backspacing an empty string results in an empty string.
  • The order of operations matters; consecutive backspaces remove multiple characters.

Intuition

A brute-force approach would involve simulating the typing process for both strings and then comparing the final results. This could be done by iterating through each character, building a new string while handling backspaces, and finally comparing the two resulting strings. However, this approach has a time complexity of O(n) per string, leading to an overall complexity of O(2n), which is acceptable but not optimal.

A more efficient approach involves using a two-pointer technique or a stack to simulate the typing process in reverse. By starting from the end of each string and moving backwards, we can efficiently handle backspaces without building intermediate strings. This reduces the space complexity to O(1) if we avoid creating additional data structures.

Approach

We will use a two-pointer technique to compare the processed versions of s and t in reverse order:

  1. Initialize two pointers, one for each string (i for s and j for t), both starting at the end of their respective strings.
  2. Define a helper function next_char(s, i) that returns the next valid character to compare by skipping over backspaces:
    • If the current character is not a backspace, return it.
    • Otherwise, count how many backspaces need to be skipped and move the pointer accordingly.
  3. Use the helper function to get the next characters from both strings.
  4. Compare the characters:
    • If they are different, return False.
    • If one of the pointers has reached the beginning of its string while the other hasn’t, return False.
  5. Move both pointers back and repeat until all valid characters have been compared.
  6. If all characters match, return True.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the longer string. We process each character at most once.
  • Space Complexity: O(1). We only use a constant amount of extra space for pointers and counters.

Solution

def backspace_compare(s: str, t: str) -> bool:
    def next_char(s, i):
        skip = 0
        while i >= 0:
            if s[i] == '#':
                skip += 1
            else:
                if skip > 0:
                    skip -= 1
                else:
                    return s[i], i - 1
            i -= 1
        return '', -1

    i, j = len(s) - 1, len(t) - 1
    while True:
        char_s, i = next_char(s, i)
        char_t, j = next_char(t, j)

        if char_s != char_t:
            return False
        if i == -1 and j == -1:
            return True
        if i == -1 or j == -1:
            return False

# Example usage:
print(backspace_compare("ab#c", "ad#c"))  # Output: True
print(backspace_compare("ab##", "c#d#"))  # Output: True
print(backspace_compare("a##c", "#a#c"))  # Output: True
print(backspace_compare("a#c", "b"))      # Output: False

Edge Cases Handled

  • Empty Strings: If both strings are empty, they are equal.
  • Strings with Only Backspaces: If a string contains only backspaces, it becomes empty.
  • Unequal Lengths: The algorithm correctly handles cases where the processed lengths of s and t differ.
  • Consecutive Backspaces: Multiple consecutive backspaces are handled by counting skips.