Minimum Remove to Make Valid Parentheses

这题最难的地方是先想通这个minimum的意义是啥. 想一下,如果一个string可以选择性的删除某些括号, 不删除某些括号然后变成Valid Parentheses, 那么说明这些不需要删除的根本不是invalid. 所以其实就是问, 怎么删除多余的括号能让Valid Parentheses.

class Solution {
    public String minRemoveToMakeValid(String s) {
        Set<Integer> set = new HashSet<>();
        Stack<Integer> st = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                st.push(i);
            }
            if(s.charAt(i) == ')') {
                if(st.isEmpty()) {
                    set.add(i);
                }
                else {
                    st.pop();
                }
            }
        }
        while(!st.isEmpty()) {
            set.add(st.pop());
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++) { 
            if(set.contains(i))
                continue;
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}