Removing Stars From a String

Problem Statement:-

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.

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

Problem Explanation with examples:-

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 <= 10<sup>5</sup>

• s consists of lowercase English letters and stars *.

• The operation above can be performed on s.

Intuition:-

• As we need to remove the last occurring non-star character when we encounter a star, a stack is suitable for this problem.

• Keep pushing the non-star characters into the stack.

• If we encounter a star, we pop the last element from the stack.

• Join the stack from bottom to top and return the string.

Solution:-

• Create a stack.

• Iterate through the string.

• If the current character is a star, we pop the last element from the stack.

• If the current character is a non-star character, we push it into the stack.

• Join the stack from bottom to top and return the string.

Code:-

JAVA Solution

public class Solution {
    public String removeStars(String s) {
        Stack<Character> st = new Stack<Character>();
        for(char i : s.toCharArray()) {
            if(i == '*' && !st.isEmpty()) {
                st.pop();
            } else {
                st.push(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!st.isEmpty()) {
            sb.append(st.pop());
        }
        return sb.reverse().toString();
    }
}

Python Solution

class Solution:
    def removeStars(self, s: str) -> str:
        st = []
        for i in s:
            if i == '*' and len(st)>0:
                st.pop()
            else:
                st.append(i)

        ans = ''.join(st)
        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(n) where n is the length of the string. We iterate through the string once.

SPACE:-

The space complexity is O(n) where n is the length of the string. We use a stack to keep track of the non-star characters.

References:-

• Stacks

Connect with me:-

• Twitter

• Github

• LinkedIn