2390.Removing_Stars_From_a_String(Medium).md

2390. Removing Stars From a String (Medium)

Date and Time: Oct 23, 2024, 22:57 (EST)

Link: https://leetcode.com/problems/removing-stars-from-a-string/

Question:

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**code". s becomes "leecode". - The closest character to the 2nd star is 'e' in "leecode". s becomes "lecode". - 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 <= 10^5

• s consists of lowercase English letters and stars *.

• The operation above can be performed on s.

Walk-through:

Use stack to store every non-star character into stack[], when we have "*", we pop the last element from stack[] to remove the star's left non-star character.

Python Solution:

Apr 23, 2026 00:21 (PDT), [ Time taken: 6m 45s ]

class Solution:
    def removeStars(self, s: str) -> str:
        # Use stack to append all char from s
        # If i == "*", pop the top element from stack to remove its left

        # TC: O(n), SC: O(n)
        stack = []
        for i in s:
            if i == "*":
                stack.pop()
            else:
                stack.append(i)

        return "".join(stack)

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