Removing Stars From a String Problem

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:

1
2
3
4
5
6
7


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:

1
2
3


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:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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.

Problem#

Examples#

Solution#

Method 1 - Using Stack#

Code#

Complexity#