1249. Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

用栈储存括号，按顺序将括号压入栈。
如果和上一个括号配对，则挤出上一个括号。

当栈不为空时，如果栈顶的符号为“)”，则优先去掉字符串左侧的括号。
如果栈顶的符号为“(”，则优先去掉字符串右侧的括号。
最后返回字符串。

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer sb = new StringBuffer(s);
        
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push('(');
            else if(s.charAt(i) == ')'){
                if(!stack.isEmpty() && stack.peek() == '(') stack.pop();
                else stack.push(')');
            }
        }
        
        while(!stack.isEmpty()){
            if(stack.pop() == ')'){
                int index = sb.indexOf(")");
                sb.delete(index, index+1);
            }
            else{
                int index = sb.lastIndexOf("(");
                sb.delete(index, index+1);
            }
        }        
        return sb.toString();
    }
}