How do you approach Backspace String Compare?

Simulate typing each string: what data structure naturally models 'undo the last character'?

What is the time complexity of Backspace String Compare?

Time complexity: O(n + m). Space complexity: O(n + m) for the stacks (O(1) for the backward-scan variant).

What are common mistakes on Backspace String Compare?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

Sitelet https://gitgood.dev/coding/backspace-string-compare

gitGood.dev

← Back to problems

Backspace String Compare

EasyData Structures

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. The character # means a backspace character.

Note that after backspacing an empty text, the text will continue to be empty.

Example 1

Input: s = "ab#c", t = "ad#c"

Output: true

Explanation: Both s and t become "ac".

Example 2

Input: s = "ab##", t = "c#d#"

Output: true

Explanation: Both s and t become "".

Example 3

Input: s = "a#c", t = "b"

Output: false

Explanation: s becomes "c" while t becomes "b".

Constraints

- 1 <= s.length, t.length <= 200 - s and t only contain lowercase letters and '#' characters.

Backspace String Compare: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Simulate typing each string: what data structure naturally models 'undo the last character'?
Push letters onto a stack; on '#', pop the top if the stack is non-empty. Then compare the two stacks.
An O(1)-space follow-up exists: scan both strings backward, counting pending backspaces to find each next surviving character.

The optimal approach

Show the approach: Stack Simulation

A backspace removes the most recently typed character - exactly a stack's LIFO behavior. For each string, push letters and pop on `#` (ignoring backspaces on an empty stack), then compare the final stacks.

A space-optimized variant walks both strings from the end, skipping characters consumed by backspaces, achieving O(1) extra space.

Time: O(n + m)
Space: O(n + m) for the stacks (O(1) for the backward-scan variant)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.

← Back to problems

Backspace String Compare

EasyData Structures

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. The character # means a backspace character.

Note that after backspacing an empty text, the text will continue to be empty.

Example 1

Input: s = "ab#c", t = "ad#c"

Output: true

Explanation: Both s and t become "ac".

Example 2

Input: s = "ab##", t = "c#d#"

Output: true

Explanation: Both s and t become "".

Example 3

Input: s = "a#c", t = "b"

Output: false

Explanation: s becomes "c" while t becomes "b".

Constraints

- 1 <= s.length, t.length <= 200 - s and t only contain lowercase letters and '#' characters.

Backspace String Compare: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Simulate typing each string: what data structure naturally models 'undo the last character'?
Push letters onto a stack; on '#', pop the top if the stack is non-empty. Then compare the two stacks.
An O(1)-space follow-up exists: scan both strings backward, counting pending backspaces to find each next surviving character.

The optimal approach

Show the approach: Stack Simulation

A space-optimized variant walks both strings from the end, skipping characters consumed by backspaces, achieving O(1) extra space.

Time: O(n + m)
Space: O(n + m) for the stacks (O(1) for the backward-scan variant)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.