Compare Strings After Simulating Backspace Characters

Easy20–25 min

Topics

StringTwo PointerStack

Companies

AmazonGoogleFacebookBloomberg

Given two strings s and t, where # means a backspace, return true if typing each string into an empty text editor produces the same result. Building each string's final contents with a stack works — push regular characters, pop on '#' — but it costs extra storage the size of both inputs. Scanning from the end of each string avoids that: resolve each pointer to the next character that survives every backspace to its right (skipping the '#' itself and however many characters it deletes), then compare those two resolved characters directly. A mismatch — or one string running out before the other — settles the answer immediately, all without ever building a final string.

Test Case 1:

Input:s = "ab#c", t = "ad#c"

Output:true

Explanation:Both reduce to "ac" once the '#' deletes the character before it.

Test Case 2:

Input:s = "ab##", t = "c#d#"

Output:true

Explanation:Both reduce to the empty string — every character gets backspaced away.

Test Case 3:

Input:s = "a#c", t = "b"

Output:false

Explanation:s reduces to "c", t is "b" — they don't match.

Constraints

◆1 ≤ s.length, t.length ≤ 200
◆s and t consist of lowercase English letters and the character '#' (backspace)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s — 2-8 chars: lowercase letters and '#'t — 2-8 chars: lowercase letters and '#'

1	class Solution {
2	public boolean compareStringsAfterBackspaces(String s, String t) {
3	int i = s.length() - 1, j = t.length() - 1;
4	while (i >= 0 \|\| j >= 0) {
5	i = nextValidIndex(s, i);
6	j = nextValidIndex(t, j);
7	if (i < 0 && j < 0) return true;
8	if (i < 0 \|\| j < 0) return false;
9	if (s.charAt(i) != t.charAt(j)) return false;
10	i--;
11	j--;
12	}
13	return true;
14	}
15	private int nextValidIndex(String str, int i) {
16	int skip = 0;
17	while (i >= 0) {
18	if (str.charAt(i) == '#') { skip++; i--; }
19	else if (skip > 0) { skip--; i--; }
20	else break;
21	}
22	return i;
23	}
24	}
25

↑i

Variables

i3

j3

INITIALIZE

Start i at the last index of s (3) and j at the last index of t (3).

Step 1 / 8

Approach & Solutions

Brute Force — Build With a Stack

Brute

Simulate typing each string into a text editor using a stack: push every regular character, and on '#' pop the last character if there is one. Do this for both strings independently to get their final, backspaced-out contents, then compare those two results directly. Simple to reason about, but it needs extra storage the size of both strings just to hold the built results.

TimeO(n + m)

SpaceO(n + m)

Java

Try it out

class Solution {
    public boolean compareStringsAfterBackspaces(String s, String t) {
        return build(s).equals(build(t));
    }
    private String build(String str) {
        StringBuilder stack = new StringBuilder();
        for (char c : str.toCharArray()) {
            if (c == '#') {
                if (stack.length() > 0) stack.deleteCharAt(stack.length() - 1);
            } else {
                stack.append(c);
            }
        }
        return stack.toString();
    }
}

Optimal — Two Pointers From the End

Optimal

Skip building either final string. Walk a pointer backward from the end of each string. At each position, first resolve it: count consecutive '#' characters and skip that many real characters before them too, landing on the next character that survives every backspace to its right (or falling off the string entirely). Compare the two resolved characters directly — a mismatch, or one string running out before the other, settles the answer immediately.