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 Sam K., 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

More Stacks practice problems

See all Stacks problems →