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

Example 2:

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

Implementations

Python

class Solution:
    def removeStars(self, s: str) -> str:
        if not s:
            return ''
        
        stack = []

        for char in s:
            if char == '*':
                stack.pop()
            else:
                stack.append(char)
        
        return ''.join(stack)

Empty String Check:

First, it checks if the string is empty. If it is, there’s nothing to do, so it returns an empty string.

Making a Stack:

It creates an empty “stack.” Think of a stack like a pile of plates. You can only add or remove plates from the top.

Going Through the String:

It goes through each character in the string, one by one.

If It’s a Star:

If the character is a star (*), it means you need to erase the previous letter. So, it removes the top element (the last letter added) from the stack.

If It’s a Letter:

If the character is a letter, it adds that letter to the top of the stack.

Putting It All Together:

After going through the entire string, the stack contains the remaining letters (the ones that weren’t erased). The code then joins those letters together to form the final result.

Typescript

function removeStars(s: string): string {
    if (!s) {
        return '';
    }

    const stack: string[] = [];

    for (const char of s) {
        if (char === '*') {
            stack.pop();
        } else {
            stack.push(char);
        }
    }

    return stack.join('');
}

Is it Empty?

First, the code looks at the line of letters and stars. If there’s nothing there at all, it says, “Okay, there’s nothing to do!” and finishes.

Making a Special Box:

It makes a special box called a “stack.” This box is like a tower where you can only put things on top and take things off the top.

Looking at Each Thing:

The code looks at each letter or star sticker in the line, one by one.

Star Sticker!

If it sees a star sticker (*), it means "oops, take away the last letter!" So, it takes the top letter out of the special box (the stack).

It’s a Letter!

If it sees a letter, it puts that letter on top of the special box (the stack).

Putting Them Together:

After looking at everything in the line, the special box (the stack) has all the letters that are left. The code then takes all those letters and puts them together to make a new word.

Go

func removeStars(s string) string {
        if len(s) == 0 {
                return ""
        }

        stack := []rune{}

        for _, char := range s {
                if char == '*' {
                        if len(stack) > 0 {
                                stack = stack[:len(stack)-1]
                        }
                } else {
                        stack = append(stack, char)
                }
        }

        return string(stack)
}

Is it Empty?

First, the code looks at the line of letters and stars. If there’s nothing there at all, it says, “Okay, there’s nothing to do!” and finishes.

Making a Special Box:

It makes a special box called a “stack.” This box is like a tower where you can only put things on top and take things off the top. In Go, it uses special characters called “runes” to hold the letters.

Looking at Each Thing:

The code looks at each letter or star sticker in the line, one by one.

Star Sticker!

If it sees a star sticker (*), it means "oops, take away the last letter!" So, it takes the top letter out of the special box (the stack). But it only does this if there are letters in the box.

It’s a Letter!

If it sees a letter, it puts that letter on top of the special box (the stack).

Putting Them Together:

After looking at everything in the line, the special box (the stack) has all the letters that are left. The code then takes all those letters and puts them together to make a new word.

If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"

DSA (Medium) — Stack — Removing Stars From a String (Python, Typescript & Go)

Implementations

Python

Typescript

Go