Backspace String Compare

Problem Statement

Given two strings s and t where # means a backspace, return true if they are equal after all backspaces are applied. A backspace on an empty text does nothing.

Example

Input:  s = "ab#c", t = "ad#c"
Output: true
Explanation: Both become "ac".

Two Pointer Approach

Scan both strings from the end. Keep a skip counter: each # increases the skip, and each real character either gets skipped (if skip > 0) or becomes the next character to compare. Compare the surviving characters one by one.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def backspaceCompare(s, t):
    def nxt(string, i):
        skip = 0
        while i >= 0:
            if string[i] == '#':
                skip += 1
            elif skip > 0:
                skip -= 1
            else:
                break
            i -= 1
        return i
    i, j = len(s) - 1, len(t) - 1
    while i >= 0 or j >= 0:
        i, j = nxt(s, i), nxt(t, j)
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False
        elif i >= 0 or j >= 0:
            return False
        i -= 1
        j -= 1
    return True

Java

int nextValid(String str, int i) {
    int skip = 0;
    while (i >= 0) {
        if (str.charAt(i) == '#') skip++;
        else if (skip > 0) skip--;
        else break;
        i--;
    }
    return i;
}
boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    while (i >= 0 || j >= 0) {
        i = nextValid(s, i);
        j = nextValid(t, j);
        if (i >= 0 && j >= 0) {
            if (s.charAt(i) != t.charAt(j)) return false;
        } else if (i >= 0 || j >= 0) return false;
        i--; j--;
    }
    return true;
}

C++

int nextValid(const string& str, int i) {
    int skip = 0;
    while (i >= 0) {
        if (str[i] == '#') skip++;
        else if (skip > 0) skip--;
        else break;
        i--;
    }
    return i;
}
bool backspaceCompare(string s, string t) {
    int i = s.size() - 1, j = t.size() - 1;
    while (i >= 0 || j >= 0) {
        i = nextValid(s, i);
        j = nextValid(t, j);
        if (i >= 0 && j >= 0) {
            if (s[i] != t[j]) return false;
        } else if (i >= 0 || j >= 0) return false;
        i--; j--;
    }
    return true;
}

Key Takeaways

• Scanning from the end lets you resolve backspaces without a stack.
• A stack-based solution is simpler but uses O(n) space.
• Carefully handle the case where one string finishes before the other.