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

Topic	Description
Two Pointers	Scan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n).
Valid Palindrome	Check whether a string reads the same forwards and backwards, ignoring case and punctuation.
Merge Sorted Array	Merge two sorted arrays into one sorted array in place.
Remove Duplicates from Sorted Array	Remove duplicate values from a sorted array in place and return the new length.
Move Zeroes	Move every zero in an array to the end while keeping the other numbers in order.
Two Sum II - Input Array Is Sorted	Find two numbers in a sorted array that add up to a target value.