LeetCode Challenge #2390. Removing Stars From a String

Question 24 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #2390. Removing Stars From a String

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 1^st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2^nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3^rd 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⁵
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

Video Solution

C++ Solution

				
					class Solution {
public:
    string removeStars(string s) {
        stack<char> st;

        for(int i=0; i<s.length(); i++)
        {
            if(s[i]=='*')
            {
                if(!st.empty())st.pop();
            }
            else st.push(s[i]);
        }

        string ans="";

        while(!st.empty())
        {
            ans+=st.top();
            st.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

Code Explanation

The purpose of this function is to process a string ‘s’ by removing characters that are followed by an asterisk (‘*’). For this execution we will consider stack data structure to efficiently handle the removal of characters.

Let’s see the step-by-step approach to the code.

First, initialise a stack of characters named ‘st’ to keep track of the characters.
Next, we will use a For Loop that iterates through each character of the string ‘s’.

- If we got a star ( * ) while iterating then we will check if the string is empty or not
- If ( !st.empty() ) if it is not empty, then we will pop the element (‘st. pop() ‘)
- If a star is not obtained we will push the elements of ‘s[ i ]’ into the stack i.e. ELSE condition because ‘s[ i ]’ is the character of the string, which is not a star.

Since stack works on the principle of LIFO ( last in first out ) we have to reverse the string for the required answer.
So, we’ll make a string ‘ans’ in which ‘ans’ stores the top element of the stack and then pops characters from the stack. The reverse result string is then returned.

Question 24 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #2390. Removing Stars From a String

Video Solution

C++ Solution

Code Explanation

Happy Coding with edSlash

Talk to our Industry Experts for Career Counselling

Company

Platform

Resources

Get in touch