AlgoMaster Logo

Backspace String Compare

easyFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have two strings where the # character acts like a backspace key. When you encounter a #, it deletes the character immediately before it (if one exists). If the text is already empty, the backspace does nothing.

Our job is to figure out whether both strings produce the same final result after processing all the backspaces.

The direct solution simulates a text editor: process each string character by character, apply backspaces as you go, then compare the two results. The follow-up asks for O(1) space, which rules out building the final strings and points to a two-pointer scan that works backwards through both inputs.

Key Constraints:

  • 1 <= s.length, t.length <= 200 → Any linear solution runs fast at this size. The interesting constraint is the follow-up: O(n) time and O(1) space.
  • s and t only contain lowercase letters and '#' characters → Every character is either a letter to type or a backspace, so there are no other cases to handle.

Approach 1: Build String with Stack

Intuition

Simulate what a text editor does. Read characters from left to right: a regular letter gets typed, and a # deletes the last character typed (if any).

A stack matches this behavior directly: push letters, pop on #. After processing both strings, whatever remains in each stack is the final text. If the two results match, return true.

Algorithm

  1. Create a helper function that takes a string and returns the "typed out" result:
    • Initialize an empty stack.
    • For each character in the string:
      • If it's a # and the stack isn't empty, pop the top element.
      • If it's a regular letter, push it onto the stack.
    • Convert the stack to a string and return it.
  2. Apply this helper to both s and t.
  3. Compare the two results. If they're equal, return true.

Example Walkthrough

The trace below types out both strings; each stack holds the editor's text so far.

s
1Start processing s = "ab#c"
0
a
i
1
b
2
#
3
c
stack (s)
1Stack for s starts empty
t
1Start processing t = "ad#c"
0
a
j
1
d
2
#
3
c
stack (t)
1Stack for t starts empty
1/6

Code

The result is correct, but each string needs a separate stack that grows and shrinks as characters arrive. The next approach runs the same simulation inside a single buffer.

Approach 2: In-Place Simulation with a Write Pointer

Intuition

The text in the editor is always a prefix of the characters kept so far, so the stack can be replaced by two indices over a single buffer: read scans the original characters, and write marks the length of the text typed so far. A letter is copied to position write, which then advances. A # moves write back one slot (if it is above zero), and the next letter overwrites the deleted character.

After the scan, the first write slots of the buffer hold the final text. Run this on both strings, then compare the two lengths and prefixes.

When strings are immutable, the buffer is a copy of the input, so this version removes the push/pop container churn rather than asymptotic space. Where the input string's own storage can be modified, no copy is needed and the forward simulation runs in O(1) extra space.

Algorithm

  1. Copy each string into a mutable buffer (or reuse the string's own storage where it is mutable).
  2. Set write = 0. For each index read from left to right:
    • If buffer[read] is #: decrement write if it is above zero.
    • Otherwise, copy buffer[read] into buffer[write] and increment write.
  3. The typed-out text is the first write characters of the buffer.
  4. Process both strings this way. Return true only if the two lengths match and the two prefixes match character by character.

Example Walkthrough

The trace below runs the read and write indices over s = "ab#c" and t = "ad#c". After the backspace, the next letter overwrites the deleted slot.

s buffer
1Copy s into a buffer. read=0, write=0
0
a
r,w
1
b
2
#
3
c
t buffer
1Copy t into a buffer. read=0, write=0
0
a
r,w
1
d
2
#
3
c
1/7

Code

Both forward passes keep the typed-out text around until the final comparison. Meeting the O(1) space bound in every language means comparing characters without storing any text, which requires scanning from the other end.

Approach 3: Two Pointers from the End (Optimal)

Intuition

A # only ever deletes characters to its left. Scanning right to left therefore meets each # before the characters it deletes, so a counter of pending backspaces is enough: increment it on #, and consume one count to skip the next letter. Scanning forward does not have this property, because a letter's survival depends on # characters that appear after it. Scanning backward, every character's fate is decided the moment the pointer reaches it.

Start one pointer at the end of each string. For each string, walk left to its next surviving character. Compare the two survivors; if they differ, return false. If one string runs out of surviving characters before the other, the final texts have different lengths, so return false. If both run out together, return true.

Algorithm

  1. Initialize pointer i at the end of s and pointer j at the end of t.
  2. Initialize skipS = 0 and skipT = 0 to count pending backspaces.
  3. Loop while i >= 0 or j >= 0:
    • Advance pointer i leftward, processing backspaces for s:
      • If s[i] is #, increment skipS and move left.
      • Else if skipS > 0, decrement skipS (skip this character) and move left.
      • Otherwise, i is at a valid character. Stop.
    • Do the same for pointer j with string t.
    • Now compare:
      • If both i >= 0 and j >= 0: compare s[i] and t[j]. If they differ, return false.
      • If one pointer is valid and the other isn't: return false.
    • Decrement both i and j to move to the next characters.
  4. If the loop finishes without returning false, return true.

Example Walkthrough

The earlier examples never stack more than one pending backspace, so this trace uses s = "a##c" and t = "#a#c". Both reduce to "c", and t starts with a backspace on empty text.

s
1Initialize: i=3, skipS=0. Start from the end of s.
0
a
1
#
2
#
3
c
i
t
1Initialize: j=3, skipT=0. Start from the end of t.
0
#
1
a
2
#
3
c
j
1/7

Code