Challenges • Asked 4 months ago by Jun
Anyone else find Dollar Sign Deletion easiest to reason about with two angles?
Quick JS snippets:
Single string transform (O(n) time, O(n) space):
js
function applyBackspaces(s) {
  const out = [];
  for (const ch of s) {
    if (ch === '$') {
      if (out.length) out.pop();
    } else {
      out.push(ch);
    }
  }
  return out.join('');
}
Two-string compare (O(n) time, O(1) extra space):
js
function equalAfterDeletes(a, b) {
  let i = a.length - 1, j = b.length - 1, skipA = 0, skipB = 0;
  while (i >= 0 || j >= 0) {
    while (i >= 0 && (a[i] === '$' || skipA > 0)) {
      if (a[i] === '$') skipA++;
      else skipA--;
      i--;
    }
    while (j >= 0 && (b[j] === '$' || skipB > 0)) {
      if (b[j] === '$') skipB++;
      else skipB--;
      j--;
    }
    const ca = i >= 0 ? a[i] : null;
    const cb = j >= 0 ? b[j] : null;
    if (ca !== cb) return false;
    i--; j--;
  }
  return true;
}
Edge cases worth testing:
- "$$a$" -> ""
- "abc$$$" -> ""
- "ab$$c" -> "c"
- compare("a$b$c", "c") -> true
If the prompt only asks for the transformed string, the stack approach is simplest. If it asks to compare two inputs post-deletion, prefer the reverse two-pointer for O(1) space.