LeetCode 844: Backspace String Compare

Problem Restatement

We are given two strings s and t.

Each string contains lowercase letters and the character "#".

The "#" character acts like a backspace in a text editor. It deletes the character immediately before it. If there is no character before it, it does nothing.

Return True if both strings become equal after applying all backspaces. Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        ...

Examples

Example 1:

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

Process s:

"ab#c" -> "ac"

Process t:

"ad#c" -> "ac"

Both final strings are equal.

So the answer is:

True

Example 2:

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

Process s:

"ab##" -> ""

Process t:

"c#d#" -> ""

Both final strings are empty.

So the answer is:

True

Example 3:

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

Process s:

"a#c" -> "c"

Process t:

"b" -> "b"

The final strings differ.

So the answer is:

False

First Thought: Build the Final Strings

The simplest solution is to simulate typing.

Use a list as a stack.

For each character:

1. If it is a letter, push it.
2. If it is "#" and the stack is non-empty, pop one character.
3. If it is "#" and the stack is empty, do nothing.

Then compare the two final stacks.

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(text: str) -> str:
            stack = []

            for ch in text:
                if ch == "#":
                    if stack:
                        stack.pop()
                else:
                    stack.append(ch)

            return "".join(stack)

        return build(s) == build(t)

This is correct and easy to read.

Problem With Extra Space

The stack solution stores the final characters of both strings.

That uses:

O(len(s) + len(t))

extra space.

The follow-up asks whether we can solve the problem with constant extra space.

We can do that by scanning both strings from right to left.

Key Insight

Backspaces delete characters to their left.

So when scanning from right to left, we can keep a counter of how many letters should be skipped.

For one string:

This lets us find the next real character in the final string without building the string.

Algorithm

Use two pointers:

Both start at the end of their strings.

Repeat while either pointer is still valid:

1. Move i left until it points to the next surviving character in s, or becomes -1.
2. Move j left until it points to the next surviving character in t, or becomes -1.
3. If both pointers are valid, compare s[i] and t[j].
4. If only one pointer is valid, the final strings differ.
5. Move both pointers one step left and continue.

If all surviving characters match, return True.

Walkthrough

Use:

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

Start from the end.

For s, the last surviving character is:

"c"

For t, the last surviving character is also:

"c"

They match.

Move left.

In s, we see "#", so skip one letter. That deletes "b". The next surviving character is:

"a"

In t, we see "#", so skip one letter. That deletes "d". The next surviving character is:

"a"

They match.

Both strings are now exhausted, so return:

True

Correctness

The helper scan for one string returns the next character that remains after applying all backspaces to the prefix ending at the current pointer.

When it sees "#", it records one pending deletion. When it sees a normal character and there is a pending deletion, that character is deleted and the pending deletion count decreases. When it sees a normal character and there is no pending deletion, that character survives.

Therefore, each helper scan finds exactly the next surviving character from right to left.

The main loop compares the surviving characters of s and t in reverse order. If any pair differs, the final strings cannot be equal. If one string has a surviving character while the other does not, the final strings also cannot be equal.

If the loop finishes without mismatch, both final strings contain exactly the same surviving characters in the same order.

Therefore, the algorithm returns the correct result.

Complexity

Let:

n = len(s)
m = len(t)

Implementation

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

        def next_valid_index(text: str, index: int) -> int:
            skip = 0

            while index >= 0:
                if text[index] == "#":
                    skip += 1
                    index -= 1
                elif skip > 0:
                    skip -= 1
                    index -= 1
                else:
                    break

            return index

        while i >= 0 or j >= 0:
            i = next_valid_index(s, i)
            j = next_valid_index(t, j)

            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

Code Explanation

The two pointers start at the end:

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

The helper function skips deleted characters:

def next_valid_index(text: str, index: int) -> int:

When it sees a backspace, it increases the number of letters to skip:

if text[index] == "#":
    skip += 1

When it sees a letter and skip > 0, that letter is deleted:

elif skip > 0:
    skip -= 1

When it sees a letter and skip == 0, that letter remains in the final string, so the helper stops.

The main loop finds the next surviving character in each string:

i = next_valid_index(s, i)
j = next_valid_index(t, j)

If both exist, compare them:

if s[i] != t[j]:
    return False

If only one exists, the final strings have different lengths:

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

After comparing, move left:

i -= 1
j -= 1

Testing

def run_tests():
    s = Solution()

    assert s.backspaceCompare("ab#c", "ad#c") is True
    assert s.backspaceCompare("ab##", "c#d#") is True
    assert s.backspaceCompare("a#c", "b") is False
    assert s.backspaceCompare("####", "##") is True
    assert s.backspaceCompare("bxj##tw", "bxo#j##tw") is True
    assert s.backspaceCompare("a##c", "#a#c") is True
    assert s.backspaceCompare("xywrrmp", "xywrrmu#p") is True

    print("all tests passed")

run_tests()

Test meaning: