Introduction

LeetCode 844 Backspace String Compare is a fantastic problem that shows up frequently in coding interviews. It combines string manipulation, stack simulation, and even has a follow-up that challenges you to solve it in O(1) space — which is what separates a good candidate from a great one.

Here is the Link of Question -: LeetCode 844

In this article we cover a plain English explanation, real life analogy, 3 Java approaches including the O(1) space two pointer solution, dry runs, complexity analysis, common mistakes, and FAQs.

What Is the Problem Really Asking?

You are given two strings s and t. Both contain lowercase letters and # characters. Think of # as the backspace key on your keyboard — it deletes the character just before it. If there is nothing to delete, it does nothing.

Process both strings through these backspace operations and check if the resulting strings are equal. Return true if equal, false otherwise.

Quick Example:

1. s = "ab#c" → # deletes b → becomes "ac"
2. t = "ad#c" → # deletes d → becomes "ac"
3. Both equal "ac" → return true ✅

Real Life Analogy — The Keyboard Typo

You are typing a message. You type "ab", realize you made a typo, hit backspace, and type "c". Your friend types "ad", hits backspace, and types "c". Even though you both typed differently, the final message on screen is the same — "ac".

That is exactly what this problem is about. Two people typing differently but ending up with the same result.

Approach 1: StringBuilder as Stack (Optimal & Clean) ✅

The Idea

This is your own solution and the best O(n) approach. Process each string independently using a StringBuilder as a stack:

1. Letter → append to StringBuilder (push)
2. # → delete last character if StringBuilder is not empty (pop)

Then simply compare the two resulting StringBuilders.

Notice how extracting a process() helper method makes the code cleaner and avoids repeating the same loop twice — a great habit to show in interviews!

Dry Run — s = "ab##", t = "c#d#"

Processing s = "ab##":

1. a → append → "a"
2. b → append → "ab"
3. # → delete last → "a"
4. # → delete last → ""

Processing t = "c#d#":

1. c → append → "c"
2. # → delete last → ""
3. d → append → "d"
4. # → delete last → ""

Both result in "" → return true ✅

Time Complexity: O(n + m) — where n and m are lengths of s and t Space Complexity: O(n + m) — two StringBuilders storing processed strings

Approach 2: Stack Based Solution (Interview Classic)

The Idea

Same logic as above but using explicit Stack<Character> objects. Great for explaining your thought process clearly in an interview even though StringBuilder is cleaner.

Dry Run — s = "a#c", t = "b"

Processing s = "a#c":

1. a → push → stack: [a]
2. # → pop → stack: []
3. c → push → stack: [c]
4. Result: "c"

Processing t = "b":

1. b → push → stack: [b]
2. Result: "b"

"c" does not equal "b" → return false ✅

Time Complexity: O(n + m) Space Complexity: O(n + m)

Approach 3: Two Pointer — O(1) Space (Follow-Up Solution) 🔥

This is the follow-up the problem asks about — can you solve it in O(n) time and O(1) space? This means no extra StringBuilder or Stack allowed.

The Idea

Instead of building processed strings, traverse both strings from right to left simultaneously. Keep a count of pending backspaces. Skip characters that would be deleted and compare characters that survive.

Why right to left? Because # affects characters to its left, so processing from the end lets us know upfront how many characters to skip.

Dry Run — s = "ab#c", t = "ad#c"

Starting from the right end of both strings:

Round 1:

1. s[3] = 'c' → valid, no skips → stop
2. t[3] = 'c' → valid, no skips → stop
3. Compare 'c' == 'c' ✅ → move both pointers left

Round 2:

1. s[2] = '#' → skipS = 1, move left
2. s[1] = 'b' → skipS > 0, skipS = 0, move left
3. s[0] = 'a' → valid, stop
4. t[2] = '#' → skipT = 1, move left
5. t[1] = 'd' → skipT > 0, skipT = 0, move left
6. t[0] = 'a' → valid, stop
7. Compare 'a' == 'a' ✅ → move both pointers left

Both pointers exhausted → return true ✅

Time Complexity: O(n + m) — each character visited at most once Space Complexity: O(1) — only pointer and counter variables, no extra storage!

Approach Comparison

The StringBuilder approach is the easiest to write and explain. The Stack approach is slightly more verbose but shows clear intent. The Two Pointer approach is the hardest to code but the most impressive — it solves the follow-up and uses zero extra space.

In an interview, start with the StringBuilder solution, explain it clearly, then mention the Two Pointer approach as the O(1) space optimization if asked.

How This Fits the Stack Simulation Pattern

You have now seen this same pattern across four problems:

3174 Clear Digits — digit deletes closest left non-digit 2390 Removing Stars — star deletes closest left non-star 1047 Remove Adjacent Duplicates — character cancels matching top of stack 844 Backspace String Compare — # deletes closest left character, then compare two strings

All four use the same StringBuilder-as-stack core. The only differences are the trigger character and what you do with the result. This is the power of pattern recognition in DSA.

Common Mistakes to Avoid

Not handling backspace on empty string When # appears but the StringBuilder is already empty, do nothing. Always guard with sb.length() > 0 before calling deleteCharAt. The problem explicitly states backspace on empty text keeps it empty.

Using Stack and forgetting to handle # when stack is empty In the Stack approach, only pop if the stack is not empty. Pushing # onto the stack when it is empty is a common bug that gives wrong answers.

In Two Pointer, comparing before both pointers find valid characters Make sure both inner while loops fully complete before comparing. Comparing too early is the most common mistake in the O(1) space solution.

FAQs — People Also Ask

Q1. What is the best approach for LeetCode 844 in Java? For most interviews, the StringBuilder approach is the best — clean, readable, and O(n) time. If the interviewer asks for O(1) space, switch to the Two Pointer approach traversing from right to left.

Q2. How does the O(1) space solution work for LeetCode 844? It uses two pointers starting from the end of both strings, keeping a skip counter to track pending backspaces. Characters that would be deleted are skipped, and only surviving characters are compared.

Q3. What is the time complexity of LeetCode 844? All three approaches run in O(n + m) time where n and m are the lengths of the two strings. The Two Pointer approach achieves this with O(1) space instead of O(n + m).

Q4. Why traverse from right to left in the Two Pointer approach? Because # affects characters to its left. Scanning from the right lets you know upfront how many characters to skip before you reach them, avoiding the need to store anything.

Q5. Is LeetCode 844 asked in Google interviews? Yes, it is commonly used as a warmup or screening problem. The follow-up O(1) space solution is what makes it interesting for senior-level interviews.

Similar LeetCode Problems to Practice Next

1. 1047. Remove All Adjacent Duplicates In String — Easy — same stack pattern
2. 2390. Removing Stars From a String — Medium — star as backspace
3. 3174. Clear Digits — Easy — digit as backspace
4. 1209. Remove All Adjacent Duplicates in String II — Medium — k adjacent duplicates
5. 678. Valid Parenthesis String — Medium — stack with wildcards

Conclusion

LeetCode 844 Backspace String Compare is a well-rounded problem that tests string manipulation, stack simulation, and space optimization all in one. The StringBuilder solution is your go-to for interviews. But always be ready to explain the Two Pointer O(1) space follow-up — that is what shows real depth of understanding.

Check out these problems alongside 1047, 2390, and 3174 and you will have the entire stack simulation pattern locked down for any coding interview.