LeetCode 2390: Removing Stars From a String

Explanation

To solve this problem, we can iterate through the string from left to right. Whenever we encounter a star, we remove the closest non-star character to its left and the star itself. We repeat this process until there are no more stars left in the string.

• We can use a stack to keep track of non-star characters encountered so far.
• When we encounter a star, we pop the top element from the stack because it is the closest non-star character to the left of the star.
• After iterating through the whole string, we reconstruct the final string using the elements left in the stack.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string.

Space Complexity

The space complexity of this solution is also O(n) due to the stack used.

public String removeStars(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '*') {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.insert(0, stack.pop());
    }
    
    return sb.toString();
}