Code Logo

Backspace String Compare

Published at23 Jul 2026
Created by
Easy 2 views
Like0

You are given two strings where the character # represents a backspace key. When you see #, it removes the character immediately before it. If there is no character before the #, nothing happens. After applying all backspaces to both strings, determine if the resulting strings are equal.

A stack handles this naturally: iterate through each character, push non-backspace characters onto the stack, and pop the top when you encounter #(if the stack is not empty). At the end, compare the two stacks.

For example, "ab#c" becomes "ac". "ad#c" also becomes "ac", so they match. But "a##c" becomes "c" because both backspaces remove the a.Applying backspaces with a stack is intuitive: non-backspace characters are pushed, and each backspace pops the most recent character. This directly models the behavior of a text editor's backspace key.An O(1) space solution exists using two pointers from the end, but the stack approach is more readable and less error-prone. For interview settings, the stack solution is preferred for clarity, and you can discuss the space-optimized version as a follow-up.The edge case of consecutive backspaces or backspaces at the beginning of the string (when the stack is empty) are handled naturally by checking if the stack is empty before popping.

Example Input & Output

Example 1
Input
s="a#c", t="b"
Output
false
Explanation

Becomes "c" vs "b".

Example 2
Input
s="ab#c", t="ad#c"
Output
true
Explanation

Both become "ac".

Example 3
Input
s="ab##", t="c#d#"
Output
true
Explanation

Both become empty string.

Algorithm Flow

Recommendation Algorithm Flow for Backspace String Compare

Solution Approach

Define a helper function that takes a string and returns the processed result. Iterate through each character. If it's not #, push it. If it's # and the stack is not empty, pop. Then compare the two resulting strings.

Time complexity is O(n). Space complexity is O(n) for the stacks.

Best Answers

java
import java.util.*;
class Solution {
    public boolean solution(String s, String t) {
        return build(s).equals(build(t));
    }
    String build(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '#') { if (!stack.isEmpty()) stack.pop(); }
            else stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        for (char c : stack) sb.append(c);
        return sb.toString();
    }
}