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.

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
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.

function build(s) {
  var stack = []
  for (var i = 0; i < s.length; i++) {
    if (s[i] === '#') { if (stack.length) stack.pop() }
    else stack.push(s[i])
  }
  return stack.join('')
}
function solution(s, t) {
  return build(s) === build(t)
}

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();
    }
}