Skip to main content

844. Backspace String Compare

easy

Compare two strings after applying backspace characters. Classic stack warm-up — with a fun O(1) space follow-up that uses two pointers from the right.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. Note that after backspacing an empty text, the text will continue empty.

Constraints

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

Examples

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".

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A backspace cancels the most recent character. That's a stack popping its top.

Hint 2

Build a stack (or a char list used as one) for each string, then compare the final stacks.

Hint 3

Edge case: a backspace on an empty stack is a no-op — don't try to pop nothing.

Hint 4

Follow-up: do it in O(1) extra space using two pointers scanning right to left, counting pending backspaces.

Solution approach

Reveal approach

Stack approach: for each string, scan left to right pushing letters and popping on '#' (if non-empty). Compare the two resulting strings. O(n+m) time, O(n+m) space. Two-pointer follow-up: walk both strings from the right with two indices and 'skip counters' that track pending backspaces. To advance to the next 'real' character: while you see '#', increment skip and step left; while you have skip > 0 and a letter, decrement skip and step left. When both pointers land on a real character, they must match — otherwise return false. Continue until both are exhausted. O(n+m) time, O(1) space. The two-pointer version is the interview-impressive variant.

Complexity

Time
O(n+m)
Space
O(1) with two pointers

Related patterns

  • stack
  • two-pointers
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Backspace String Compare and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →