# 1249. Minimum Remove to Make Valid Parentheses
###### tags: `Leetcode` `Medium` `Parentheses`
## 思路一 $O(N)$ $O(1)$
首先记录一共有几个右括号
每次遇到右括号，右括号个数-1，这样当下次碰到左括号的时候，close记录的就是后面还有几个右括号，如果open个数是0，就说明前面没有左括号跟它匹配，因此直接continue，否则匹配成功，剩余的左括号（open）-1
每次遇到左括号，如果后面没有右括号（close==0），直接continue，否则open+1，等待后面与它匹配的右括号
### 思路二 $O(N)$ $O(N)$
Stack记录'('的位置
遇到')'就pop掉 留下的就是要删掉的'('
对于要删掉的')'直接在过程中加进set即可
## Code
### 思路一

class Solution {
    public String minRemoveToMakeValid(String s) {
        int close = 0;
        int open = 0;
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i)==')') close++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i)=='('){
                if(close==open) continue;
                open++;
            }
            if(s.charAt(i)==')'){
                close--;
                if(open==0) continue;
                open--;
            }
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

### 思路二

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