Description​

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.

Video Explanation​

Watch

Approach​

To solve this problem, we can use a stack to keep track of the non-star characters. We iterate through the string, and for each character:

1. If it is a non-star character, push it onto the stack.
2. If it is a star (*), pop the top element from the stack (i.e., remove the closest non-star character).

Finally, the remaining elements in the stack represent the string after all stars and corresponding characters have been removed.

Solutions​

class Solution {
public:
    string removeStars(string s) {
        string res = "";
        for (char c : s) {
            if (c == '*') {
                if (!res.empty()) res.pop_back();
            } else {
                res.push_back(c);
            }
        }
        return res;
    }
};

class Solution {
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '*') {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        
        for char in s:
            if char == '*':
                if stack:
                    stack.pop()  # Remove the closest non-star character
            else:
                stack.append(char)
        
        return ''.join(stack)

var removeStars = function(s) {
    const stack = [];
    for (const char of s) {
        if (char === '*') {
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    return stack.join('');
};