# 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

| Item | Meaning |
|---|---|
| Input | Two strings `s` and `t` |
| Output | `True` if final typed strings are equal |
| Backspace | `"#"` deletes the previous typed character |
| Empty text | Backspace on empty text has no effect |
| Follow-up | Solve in `O(n)` time and `O(1)` space |

Function shape:

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

## Examples

Example 1:

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

Process `s`:

```python
"ab#c" -> "ac"
```

Process `t`:

```python
"ad#c" -> "ac"
```

Both final strings are equal.

So the answer is:

```python
True
```

Example 2:

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

Process `s`:

```python
"ab##" -> ""
```

Process `t`:

```python
"c#d#" -> ""
```

Both final strings are empty.

So the answer is:

```python
True
```

Example 3:

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

Process `s`:

```python
"a#c" -> "c"
```

Process `t`:

```python
"b" -> "b"
```

The final strings differ.

So the answer is:

```python
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.

```python
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:

```python
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:

| Character | Action |
|---|---|
| `"#"` | Increase skip count |
| Letter and skip count > 0 | Skip this letter and decrease skip count |
| Letter and skip count == 0 | This letter survives |

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

## Algorithm

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Current index in `s` |
| `j` | Current index in `t` |

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:

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

Start from the end.

For `s`, the last surviving character is:

```python
"c"
```

For `t`, the last surviving character is also:

```python
"c"
```

They match.

Move left.

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

```python
"a"
```

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

```python
"a"
```

They match.

Both strings are now exhausted, so return:

```python
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:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` | Each character is processed at most once |
| Space | `O(1)` | Only pointers and skip counters are used |

## Implementation

```python
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:

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

The helper function skips deleted characters:

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

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

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

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

```python
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:

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

If both exist, compare them:

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

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

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

After comparing, move left:

```python
i -= 1
j -= 1
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"ab#c"` vs `"ad#c"` | Confirms normal deletion |
| `"ab##"` vs `"c#d#"` | Confirms both become empty |
| `"a#c"` vs `"b"` | Confirms different final strings |
| Many backspaces | Confirms empty text stays empty |
| Consecutive backspaces | Confirms multiple deletions |
| Leading backspace | Confirms backspace on empty text has no effect |
| Deletion near end | Confirms right-to-left scan handles suffixes |