[LeetCode] Removing Stars From a String

Problem: 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:

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

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

Approach: We can use stack here to solve this issue. We just need to iterate through the given string s and for every character we need to see if it is not '*' then push otherwise pop. After the loop ends, we need to pop all the remaining characters in the stack, store it in the string and reverse it. That will be our answer,

Just to save the space we can use the result string itself as stack like we did it in Remove All Adjacent Duplicates.

That's all!

Implementation in C#:

    public string RemoveStars(string s)

    {

        char[] stack = s.ToCharArray();

        int stackTop = -1;

        foreach (char ch in s)

        {

            if (ch != '*')

            {

                stack[++stackTop] = ch;

            }

            else

            {

                if (stackTop != -1)

                {

                    --stackTop;

                }

            }

        }

        if (stackTop == -1)

        {

            return "";

        }

        return new string(stack, 0, stackTop + 1);

    }

Complexity: O(n)