2390. Removing Stars From a String-Leetcode

2390. Removing Stars From a String-Leetcode

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.

Solution :

Intuition

We are given a string and some stars in that string. For every star, we have to remove the previous character from the string.

Just thought about the backspace on your keyboard. These stars are just representing the backspace button of your laptop keyboard.

When you will get the star in the string you just have to remove the last character means the character that is just behind the star.

Approach

We are going to use a stack to solve this problem because we need to track the closest nonstar character to the left of each star. When we encounter the star, we want to remove both the previous character and the star.

To keep track of this information we are using stack.

Now, iterate through the string and check if we are getting a character or a star. If we are getting a character, then we need to append it to the stack and if we are getting a start then we need to pop the last character from the stack.

When we are iterating through the string and appending the characters to the stack. Then we can access the last character on top of the stack easily.

For the previous character that we have pushed into the stack like in “ xy* “, first we will push x to stack, then y to stack and when we will get a star, we can easily get the previous character from the top of the stack using stack.pop() in python.

After completing the iteration, the stack will give us the answer.

Why does this solution/approach work?

The stack keeps track of the non-star characters that need to be removed for each star, and popping the top element from the stack removes the closest non-star character to the left of the current star.

Example :

string = “xy*z”

Steps

  1. Initialize a stack -> stack = []

  2. Iterate through the string

  3. Check if the item at i index is a character or star

  4. If char append it to the stack otherwise remove the last item from the stack.

  5. After completing iterations (loop), the stack will give us the answer.

Dry Run :

  1. In the first iteration, we are getting “x”. So, “x” is a character and not a star. Now, just push the “x” into the stack. Now the stack looks like this -> stack = [“x”]

  2. In the second iteration, we are getting “y”. As “y” is a character and not a star, so we are just appending it to stack. Now the stack will look like this -> stack = [“x”,”y”]

  3. In the third iteration, we are getting “*”. So, we are getting a star in this iteration, now we all know what we have to do. We just have to remove the last character. The last character was “y” so just pop the last item from the stack which will remove “y”. Now stack will look like this -> stack = [“x”]

  4. In the fourth and the last iteration, we are getting “z”. As “z” is a character and not a star, we are just appending it to the stack and the stack will look like this -> stack = [“x”,”z”]

Now we moved out of the loop and the stack=[“x”,”z”] is giving us the answer.

Just convert the stack to string and return it.

Complexity

  • Time complexity:

The time complexity of the above algorithm is O(N).

  • Space complexity:

The space complexity of the above algorithm is O(N)

Code

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            if s[i] != "*":
                stack.append(s[i])
            else:
                stack.pop()
        return "".join(stack)

If you have any feedback or suggestions on how I can improve this solution or explanation, please let me know in the comments. Thanks! 😊

Data Structures Algorithms Stack Leetcode Leetcode Solution