Challenges • Asked 2 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.