Backspace String Compare

easy two pointers string stack simulation

Problem

Given two strings s and t, return whether they are equal when both are typed into empty text editors where '#' is a backspace.

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

Outputtrue

Both reduce to "ac".

def backspaceCompare(s, t):
    i, j = len(s) - 1, len(t) - 1
    while i >= 0 or j >= 0:
        i = skip(s, i)
        j = skip(t, j)
        a = s[i] if i >= 0 else ""
        b = t[j] if j >= 0 else ""
        if a != b: return False
        i -= 1; j -= 1
    return True

def skip(s, i):
    back = 0
    while i >= 0 and (s[i] == "#" or back > 0):
        back += 1 if s[i] == "#" else -1
        i -= 1
    return i

function backspaceCompare(s, t) {
  const skip = (str, i) => { let b = 0; while (i >= 0 && (str[i] === '#' || b > 0)) { b += str[i] === '#' ? 1 : -1; i--; } return i; };
  let i = s.length - 1, j = t.length - 1;
  while (i >= 0 || j >= 0) {
    i = skip(s, i);
    j = skip(t, j);
    const a = i >= 0 ? s[i] : '';
    const b = j >= 0 ? t[j] : '';
    if (a !== b) return false;
    i--; j--;
  }
  return true;
}

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        while (i >= 0 || j >= 0) {
            i = skip(s, i);
            j = skip(t, j);
            char a = i >= 0 ? s.charAt(i) : 0;
            char b = j >= 0 ? t.charAt(j) : 0;
            if (a != b) return false;
            i--; j--;
        }
        return true;
    }
    int skip(String s, int i) {
        int back = 0;
        while (i >= 0 && (s.charAt(i) == '#' || back > 0)) {
            back += s.charAt(i) == '#' ? 1 : -1;
            i--;
        }
        return i;
    }
}

bool backspaceCompare(string s, string t) {
    auto skip = [](const string& s, int i){ int b = 0; while (i >= 0 && (s[i] == '#' || b > 0)) { b += s[i] == '#' ? 1 : -1; i--; } return i; };
    int i = (int)s.size() - 1, j = (int)t.size() - 1;
    while (i >= 0 || j >= 0) {
        i = skip(s, i);
        j = skip(t, j);
        char a = i >= 0 ? s[i] : 0;
        char b = j >= 0 ? t[j] : 0;
        if (a != b) return false;
        i--; j--;
    }
    return true;
}

Explanation

Each # acts like a backspace. We could rebuild both strings, but the slick trick is to compare them from the right end with two pointers, using only O(1) extra space.

The helper skip walks one pointer leftward past any deleted characters. It keeps a counter back: every # adds one pending backspace, and every normal letter either cancels a pending backspace or, if none are pending, is the real next character.

The main loop calls skip on both strings to land each pointer on its next surviving character, then compares them. If they differ, the strings are not equal; if both run out together with all matches, they are equal.

Example: s = "ab#c", t = "ad#c". From the right both surface c, then the # deletes b in s and d in t, leaving a on each side. Everything matches, so the answer is true.

Scanning right to left lets a backspace cancel the character just before it naturally, so we never build the final strings at all.

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