Crack the Backend

Problem Statement

Given two strings s and t, return true if they are equal when both are typed into empty text editors. # represents a backspace character: when we type #, it deletes the previous character (if any). Compare the final strings after processing all backspaces.

For example, s = "ab#c" becomes "ac" (b is deleted). t = "ad#c" becomes "ac", so they are equal.
We can simulate from the end of each string: skip characters that are "consumed" by backspaces, then compare the effective character. This avoids building the full string and uses O(1) extra space.

Key Observations

Two pointers from the end: For each string we maintain an index and a "skip" count (number of backspaces we have to apply). When we see #, we increment skip and move left. When we see a normal character, if skip > 0 we decrement skip and move left (this character is "deleted"); else this is the next "effective" character from the right. We get the next effective character from s and from t and compare them. If they differ, return false. If we exhaust both strings and all comparisons matched, return true.
We need a helper that, given an index and a string, returns the next effective character (and updates the index), or signals that the string is exhausted.

Approach

High-level: Iterate from the end of both strings. For each string, skip characters that are "deleted" by backspaces (count # and skip that many non-# characters). Compare the current "effective" character from s and t. If they differ, return false. If one string is exhausted before the other, return false. Return true if both are exhausted together and all compared chars matched.

Steps:

i = s.length()-1, j = t.length()-1. While i >= 0 || j >= 0: get next effective char from s (move i left, skipping backspaced chars), get next effective char from t (move j). If the two chars differ, return false.
If one string has remaining effective chars and the other doesn't, return false. Return true.

Implementation

Java

public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;

    while (i >= 0 || j >= 0) {
        int skip = 0;

        while (i >= 0 && (s.charAt(i) == '#' || skip > 0)) {
            if (s.charAt(i) == '#') {
                skip++;

                } else {
                skip--;
            }

            i--;
        }

        skip = 0;

        while (j >= 0 && (t.charAt(j) == '#' || skip > 0)) {
            if (t.charAt(j) == '#') {
                skip++;

                } else {
                skip--;
            }

            j--;
        }

        if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {
            return false;
        }

        if ((i >= 0) != (j >= 0)) {
            return false;
        }

        i--; j--;
    }

    return true;
}

Test Cases

Example 1

Input

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

Expected

true

Explanation

Both become "ac".

Complexity Analysis

Time: O(n+m).
Space: O(1).

Follow-ups

Build the final string with a stack; compare (O(n) space).