Typed With Backspaces

EasyTwo Pointers

Problem

Two people type into identical text boxes. Their keystroke logs are a and b, where a lowercase letter types that letter and # is a backspace that deletes the previous character (a backspace on an empty box does nothing).

Return true if both boxes end up with the same text. Aim for O(1) extra memory.

Example 1

Input:
a = "ab#c", b = "ad#c"
Output:
true

Both end up as "ac".

Example 2

Input:
a = "a##b", b = "#b"
Output:
true

Both end up as "b".

Example 3

Input:
a = "xy#", b = "x#y"
Output:
false

"x" versus "y".

Constraints

  • 0 ≤ a.length, b.length ≤ 10^5
  • a and b contain lowercase letters and '#'

Hint

Show the first hint

Simulating with a stack works but uses O(n) memory. Which direction makes a backspace easy to apply?

Walkthrough

How to approach it

01Clarify before coding

  • What does a backspace on an empty box do? Nothing.
  • Can the logs have different lengths? Yes, and they can still produce the same text.
  • Is O(n) memory acceptable? It works, but the target is O(1).

02Brute force

Build each final text with a stack (push letters, pop on '#') and compare the two results.

Cost: O(n + m) time and O(n + m) memory for the two built strings.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.