class Solution {
    // time O(n)
    // space O(n)
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '*') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            }
            else {
                stack.push(c);
            }
        }


        StringBuilder sb = new StringBuilder(stack.size());
        sb.setLength(stack.size());
        for (int i = stack.size() - 1; i >= 0; i--) {
            sb.setCharAt(i, stack.pop());
        }

        return sb.toString();
    }
}