← DSA Atlas
Dedicated problem page · #844

Backspace String Compare

EasyTwo PointersReverse scan resolving backspacesTwo pointers
Solve on LeetCode ↗
844
EasyTwo PointersTwo pointersReverse scan resolving backspaces

Backspace String Compare

Given two strings s and t where '#' means a backspace that deletes the preceding character, return true if the two strings are equal after all backspaces are applied. A backspace on an empty text does nothing.

Open official problem prompt ↗
In plain English

Determine whether two texts typed with a backspace key produce the same final string, without materializing those final strings.

Picture it like this

Proofreading two edited documents from the last word backward; every 'delete' mark you meet cancels the next word you would otherwise read, so you only compare the words that actually survived.

Example
Input
s = "ab#c", t = "ad#c"
Output
true
Why
Both reduce to "ac": "ab#c" deletes 'b', "ad#c" deletes 'd'.
Constraints
1 <= s.length, t.length <= 200s and t only contain lowercase letters and '#' characters
Pattern lesson

See the pattern, then code

Reverse scan resolving backspaces
Recognition clue

A '#' erases the character just before it, and its effect depends on what precedes it — reading from the right lets each backspace announce itself before the characters it would delete, which is the signal for a reverse two-pointer scan.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Scanning right-to-left, a '#' tells you in advance to skip the next real character. Track a skip counter per string, land each pointer on the next surviving character, and compare those survivors in lockstep.

New words, made simpleKnow these before the algorithm
Backspace
The '#' symbol, which removes the character immediately before it.
Skip counter
A running count of pending deletions owed as you scan leftward.
Surviving character
A letter not cancelled by any backspace.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Build both strings with a stack

Correct and readable, but uses extra space proportional to the inputs.

Push letters and pop on '#', then compare the two results.

Time O(n + m)Space O(n + m)
Best choiceReverse two-pointer with skip counts

Same time with constant extra space — the interview-preferred answer.

Walk from the ends, resolving backspaces on the fly, comparing survivors directly.

Time O(n + m)Space O(1)
The rule we keep true

Invariant

Whenever both pointers pause, each rests on a character that is guaranteed to survive all backspaces to its right, and every surviving pair already compared was equal.

Why this is correct

Reasoning

Reading right-to-left, a '#' is seen before the character it deletes, so a simple counter can absorb the correct number of subsequent letters. Each pointer therefore visits exactly the characters that remain in the final text, in the same reversed order. Comparing them pairwise is equivalent to comparing the fully-processed strings, and a length difference surfaces as one pointer running out first.

The algorithm in three movesSay these aloud before coding
1Point i and j at the ends of s and t

s tail: 'c' kept; then '#' sets skip=1, so 'b' is deleted; 'a' kept -> "ac"

2For each string, walk left past '#'s (incrementing a skip count) and past characters the skips consume, stopping on the next kept character

t tail: 'c' kept; '#' skips 'd'; 'a' kept -> "ac"

3Compare the two surviving characters; mismatch or a lone survivor means unequal

survivors compared: 'c'='c', 'a'='a' -> true

4Step both pointers left and repeat until both are exhausted

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
a0
b1
#2
c3
1 · Reads[3]='c', t[3]='c'
2 · AskWhat is the first surviving char from each right end?
3 · Update statei=3, j=3, skip=0
4 · ResultBoth 'c' survive; compare equal, step to i=2, j=2.
Key takeaway

In "ab#c" the '#' at index 2 cancels the 'b' at index 1, leaving "ac".

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-14next_valid helper

    From a position, absorb '#'s into a skip count and consume that many letters, returning the index of the next kept character (or -1).

  2. 2
    Lines 15-16Initialize tail pointers

    Start comparison from the last index of each string.

  3. 3
    Lines 17-26Lockstep survivor comparison

    Advance both pointers to survivors; a mismatch or exactly one exhausted pointer means the texts differ.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Leading backspaces like "#a" — a '#' with nothing before it is a no-op and must not underflow
  • One string empties entirely (e.g. "a#" vs "") — both should reduce to the same empty text
  • Strings of different raw length that collapse to equal texts ("ab##" vs "c#d#") both become empty
  • A survivor in one string but exhaustion in the other must return false
!

Common beginner mistakes

  • Decrementing the skip counter below zero, or treating a '#' on empty text as deleting a real character
  • Comparing raw lengths of s and t instead of the processed survivors
  • Handing the 'one pointer exhausted, one not' case incorrectly and returning true
Check your understanding

Why scan from the right instead of the left?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima