# AlgoDaily 13: Dollar Sign Deletion

“You’re given an array of strings containing alphabetical characters and certain \$ characters. A \$ represents a DELETE action whereby the character before it is deleted.

Each of these strings will be run through a method to operate on the \$ DELETE action. We want to find out if the final string is the same for all of them. Let’s take an example:”

``````const input = ["f\$st", "st"]
isDollarDeleteEqual(input);
// true
// true because both become "st"
``````

“Given the below function signature, can you find a solution in O(n) time and constant space?”

``````function isDollarDeleteEqual(arr) {
return;
}

function getFinalStr(str) {
return str;
}
``````

Again I don’t think these function names are great. Also it’s not clear whether the `O(n)` requirement is for the `isDollarDeleteEqual()` function or the `getFinalStr()` function, nor why we’re implementing the `isDollarDeleteEqual` function at all when the task seems focused only on `getFinalStr()`.

Looks like it’s `getFinalStr()` that has to be `O(n)`.

This is another one where a stack seems natural for pushing and popping as we iterate:

``````function getFinalStr(str) {
const stack = [];
for (let char of str) {
if (char === "\$") {
stack.pop();
continue;
}
stack.push(char);
}
return stack.join("");
}
``````

Then we just use that function to compare strings:

``````function isDollarDeleteEqual(arr) {
let prev;
for (let current of arr) {
current = getFinalStr(current);
if (prev !== undefined && current !== prev) {
return false;
}
prev = current;
}
return true;
}
``````

The above works fine.

Algo Daily also has a solution which involves iterating on the string backwards, and skipping a character when we hit a \$. This is still `O(n)` but avoids having to copy the string into a stack, which is more memory-efficient.

View post: AlgoDaily 13: Dollar Sign Deletion