#844 Backspace String Compare

frequently reported atGoogle Microsoft Amazon Meta

the problem

In plain words

Two strings s and t are typed into empty text boxes, where '#' means Backspace. A Backspace on an empty box does nothing. Return true if both boxes end up holding the same text.

in s = "ab#c", t = "ad#c"

out true

Both become "ac".

in s = "ab##", t = "c#d#"

out true

Both become empty.

in s = "a#c", t = "b"

out false

"c" is not "b".

1 ≤ s.length, t.length ≤ 200
Only lowercase letters and '#'
Follow-up: O(n) time and O(1) extra space

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Typing with Backspace is a stack: a letter pushes, '#' pops. For O(1) space, read from the end instead: every '#' tells you to skip one of the letters before it, so you can produce the surviving letters one by one and compare as you go.

solutions

From brute force to optimal

Replay the keys: append letters, delete the last character on '#'. Compare the two results.

For each key: letter → append; '#' → deleteCharAt(length − 1) if not empty.
Do it for s and for t.
Compare with equals.

timeO(n + m)

Each key is handled once; deleting the last character of a StringBuilder is O(1).

spaceO(n + m)

The two typed strings.

javajava.util.*

1class Solution {2    public boolean backspaceCompare(String s, String t) {3        return type(s).equals(type(t));4    }5 6    /** Replays the keystrokes. The end of the builder is the top of a stack. */7    private String type(String keys) {8        StringBuilder typed = new StringBuilder();9        for (char c : keys.toCharArray()) {10            if (c != '#') typed.append(c);                                       // push11            else if (typed.length() > 0) typed.deleteCharAt(typed.length() - 1); // pop ('#' on empty does nothing)12        }13        return typed.toString();14    }15}

From the end of each string, skip characters erased by later '#'s to find the next survivor. Compare survivors pair by pair.

i, j start at the last index of s and t.
Move each pointer left: '#' → skip++; a letter while skip > 0 → skip−−; else stop — that letter survives.
If one string runs out first → false. Different survivors → false. Otherwise step both left and repeat.

timeO(n + m)

Each pointer only moves left, once per character.

spaceO(1)

Two indices and two skip counters.

javajava.util.*

1class Solution {2    public boolean backspaceCompare(String s, String t) {3        int i = s.length() - 1, j = t.length() - 1;4        while (i >= 0 || j >= 0) {5            i = nextKept(s, i);                        // next character that survives, or -16            j = nextKept(t, j);7            if (i < 0 || j < 0) return i < 0 && j < 0; // one string ran out: equal only if both did8            if (s.charAt(i) != t.charAt(j)) return false;9            i--;10            j--;11        }12        return true;13    }14 15    /** Walks left from i, skipping characters that a later '#' erases. */16    private int nextKept(String keys, int i) {17        int skip = 0;                                  // how many '#' are still waiting to erase18        while (i >= 0) {19            if (keys.charAt(i) == '#') skip++;20            else if (skip > 0) skip--;                 // this character is erased21            else break;                                // a survivor22            i--;23        }24        return i;25    }26}

in the room

How to say it in the interview

talk track

Give the stack version first — it's two short loops and clearly correct.
For the O(1) follow-up, explain why the end is easier: going forward you can't know whether a letter survives, going backward you already know how many '#' are waiting.
Test aloud with "ab##" vs "c#d#" and with a '#' on an empty box.

traps

Deleting on '#' when the builder is empty — deleteCharAt(-1) throws.
In the backward scan, stopping when only one string runs out and returning true.
Using String concatenation and substring in a loop: every step copies the whole string.

what they ask next

Follow-ups

What if the editor also had a Delete key that removes the character after the cursor?

Then you need a real cursor: two stacks (text left of the cursor and text right of it) — the same idea as an editor's gap buffer.

before you submit

Edge cases to test

A '#' on an empty box does nothing: "#a" types "a".
Both may type nothing at all: "ab##" and "c#d#" → true.
Only one side runs out: "abc" vs "abc#" → false.

practise next