AlgoDaily 13: Dollar Sign Deletion

2018-06-05 (Tuesday) | 300 words (~2 minutes reading)

Notes to myself.

“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.


Tech mentioned