[LeetCode] 2390. Removing Stars From a String

1. 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**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.
 

2. Thoughts

This question seems to have me use "stack"
However, since I am not use to it in python, I will first use simple algo.
Traverse string while exsists,
concat string with before + * after

3. Tips learned

4. My solution

class Solution:
    def removeStars(self, s: str) -> str:
        while "*" in s:
            star_index = s.find("*")
            s = s[: star_index - 1] + s[star_index + 1 :]
            # print(s)

        return s

65/65 cases passed (3990 ms)
Your runtime beats 5.01 % of python3 submissions
Your memory usage beats 71.42 % of python3 submissions (17.7 MB)

5. AI Solution and Improvements

Your solution works, but it can be made more efficient and Pythonic. The current approach involves repeatedly searching for the first occurrence of a star, slicing the string, and concatenating the remaining parts. This process can be inefficient for long strings because string concatenation and the find method in Python are both (O(n)) operations, where (n) is the length of the string.

A more efficient approach is to use a stack data structure. Here's how it can be done:
1. Initialize an empty list to serve as a stack.
2. Iterate over each character in the input string.
3. If the character is not a star, push it onto the stack.
4. If the character is a star, pop the top character from the stack (since we are assured by the problem statement that the operation is always possible, we don't need to check if the stack is empty).
5. Finally, join the characters in the stack to form the resulting string.

This method is more efficient because stack operations are (O(1)), and we avoid repeatedly creating new strings.

Here's the improved Python code:

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for char in s:
            if char == '*':
                stack.pop()
            else:
                stack.append(char)
        return ''.join(stack)

This code will achieve the same result but with better performance, especially for longer strings.