Backspace String Compare

1. Define the problem

Given two strings s and t, each containing lowercase letters and the character "#" (a backspace that deletes the previous character), return true if the two strings are equal once all the backspaces are applied. Rather than building the processed strings, walk both strings from the end with two pointers , skipping characters cancelled by pending backspaces as you go.

Constraints

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

Example

Inputs = "ab#c", t = "ad#c"

Outputtrue

Explanation Both strings become "ac" after applying the backspaces.

2. Visualize the solution

Walk both strings backward, skipping cancelled characters

Statusinit

i=3 ('c') and j=3 ('c') on t — no pending backspace, they match. Both pointers move left.

What happens in this step

i = 3 (value 'c'), j = 3 (value 'c')
s[i] == t[j]

No pending backspace at either index; 'c' matches 'c'. Both pointers move to index 2.

Step 1 of 4

Steps to visualize

Place a pointer at the last index of each string.
Walk each pointer backward, skipping any character cancelled by a pending "#".
Compare the characters the two pointers land on; if they differ, return false.
Move both pointers one step further back and repeat.
If both pointers are exhausted at the same time with no mismatch, the strings are equal.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk both strings backward, skipping cancelled characters

Statusinit

i=3 ('c') and j=3 ('c') on t — no pending backspace, they match. Both pointers move left.

What happens in this step

i = 3 (value 'c'), j = 3 (value 'c')
s[i] == t[j]

No pending backspace at either index; 'c' matches 'c'. Both pointers move to index 2.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function nextValidIndex(str, index) {
  let skip = 0;

  while (index >= 0) {
    if (str[index] === '#') {
      skip++;
      index--;
    } else if (skip > 0) {
      skip--;
      index--;
    } else {
      break;
    }
  }

  return index;
}

function backspaceCompare(s, t) {
  let i = s.length - 1;
  let j = t.length - 1;

  while (i >= 0 || j >= 0) {
    i = nextValidIndex(s, i);
    j = nextValidIndex(t, j);

    if (i >= 0 && j >= 0) {
      if (s[i] !== t[j]) {
        return false;
      }
    } else if (i >= 0 || j >= 0) {
      return false;
    }

    i--;
    j--;
  }

  return true;
}

Time: O(n + m)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`s = "ab#c", t = "ad#c"`	`true`	example from the docstring
`s = "#a#c", t = "a#c"`	`true`	a backspace with nothing before it to delete still resolves correctly
`s = "xy#z", t = "xzz"`	`false`	strings that collapse to different processed lengths
`s = "####", t = ""`	`true`	a string made entirely of backspaces collapses to empty
`s = "a", t = "a"`	`true`	smallest valid input, no backspaces at all
`s = "a#c", t = "b"`	`false`	differing content after backspaces are applied

Backspace String Compare