Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Dollar Sign Deletion — simple stack vs O(1) two-pointer

Challenges • Asked 2 months ago by Jun

Jun Commented on Jul 04, 2025:

Anyone else find Dollar Sign Deletion easiest to reason about with two angles?

  • Single string transform: iterate once, treat result as a stack (list). Push letters, pop on '$'.
  • Compare-two-strings variant: walk from right to left with skip counters; no extra space.

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.