Problem

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.

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 "lee**t****cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "le**e***cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "leco**d***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.

Solution

Method 1 - Using Stack

Given a string s which contains stars (*), we need to iteratively remove the closest non-star character to the left of each star, as well as the star itself. Here’s the structured approach:

  1. Using a Stack:
    • A stack is an appropriate data structure for this problem because it allows us to efficiently keep track of characters and remove the closest non-star character when we encounter a star.
    • Traverse the string from left to right. Push non-star characters onto the stack.
    • When encountering a star (*), pop the stack to remove the most recent non-star character, and then continue.
  2. Result Construction:
    • After processing the entire string, the stack will contain the characters of the final resulting string with all necessary removals applied.
    • Convert the stack back to a string to obtain the final result.

Code

Java
public class Solution {
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : s.toCharArray()) {
            if (ch == '*') {
                stack.pop(); // Remove the closest non-star character
            } else {
                stack.push(ch);
            }
        }
        
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pop());
        }
        
        return ans.reverse().toString();
    }
}
Python
class Solution:
    def removeStars(self, s: str) -> str:
        stack: List[str] = []
        
        for ch in s:
            if ch == '*':
                stack.pop()  # Remove the closest non-star character
            else:
                stack.append(ch)
        
        return ''.join(stack)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s. The stack operations (push and pop) are O(1), and we traverse the string once.
  • 🧺 Space complexity: O(n),  in the worst case where no stars are present, and all characters are pushed onto the stack.