June 16th 2023

Removing Stars From a String — Typescript

Problem Description

You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s. Remove the closest non-star character to its left, as well as remove the star itself. Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible. It can be shown that the resulting string will always be unique.

Example 1:

Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Solution 1

// Return the position of the closest start
// Returns -1 if no stars are left in the string
function closestStar(s: string): number {
    return s.indexOf("*")
}

type StarRemovalOperation = {
    // The string after the star and the character immediately to the left
    // have been removed
    newString: string,

    // The character that was immediately to the left of the star
    character: string,
}

function removeStarAtPosition(s: string, position: number): StarRemovalOperation {
    const char = s[position - 1]
    return {
        character: char,
        newString: s.replace(`${char}*`, "")
    }
}

function removeStars(s: string): string {
    let inputString = s;
    let posOfClosestStar = closestStar(inputString)

    while (posOfClosestStar != -1) {
        const removed = removeStarAtPosition(inputString, posOfClosestStar)
        inputString = removed.newString
        posOfClosestStar = closestStar(inputString)
    }

    return inputString
};

Discussion 1

This solution closely follows the algorithm laid out in the problem description. If I was on a team and a product person had outlined the algorithm this is what I would want to ship. I like it because it's debuggable and it follows the mental model.

But it's also slow

Solution 2

function removeStars(s: string): string {
    var result = s;
    while (result.includes("*")) {
        result = result.replace(new RegExp("[a-z][*]", "g"), "")
    }
    return result
};

Discussion 2

This is faster and it still mostly follows the mental model. But it's also still not fast enough.

Solution 3

function removeStars(s: string): string {
    var result: string[] = []

    for (var char of s.split("")) {
        if (char == "*") {
            result.pop()
        } else {
            result.push(char)
        }
    }

    return result.join("")
};

Discussion 3

This treat the input as a command string and the result as a stack to push and pop from. It's slightly different than the way the algorithm was outlined. If this was a bit of code that was in a critical path (like in the middle of an HTTP request) or was run on large data this would be the one I shipped.