2390. Removing Stars From a String Medium

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 "lee**t*code". s becomes "leecode".
• The closest character to the 2nd star is 'e' in "leecode". 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.

Approach

Input: A string s containing * characters

Output: Return the string after removing all stars, requiring that removing a star also removes the closest non-star character to its left.

This problem belongs to the Basic Stack category.

We use a stack stack to save the final character results. While traversing the string, whenever we encounter a non-star character, we push it into the stack; when we encounter a star *, we pop the last character from the stack.

Finally, joining the stack together yields the result.

Implementation

python

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []  # Use a stack to save the final character results

        # Traverse every character in the string
        for c in s:
            if c == '*':
                # A star means deleting the previous character, pop top of the stack
                if stack:
                    stack.pop()
            else:
                # Normal characters are pushed into the stack
                stack.append(c)
        
        # Finally, join the remaining characters in the stack to form the result string
        return ''.join(stack)

javascript

/**
 * @param {string} s
 * @return {string}
 */
const removeStars = function(s) {
    const stack = [];

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

    return stack.join('');
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

2390. Removing Stars From a String (English)

2390. 从字符串中移除星号 (Chinese)