1249 Minimum Remove to Make Valid Parentheses

Leetcode

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.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

---

用一个队列记录不合法括号的 index ，遇到左括号是放入队尾，遇到右括号时，如果队尾是左括号，他们可以抵消，否则放入队尾。重新生成字符串，遇到原字符串在队列中存在的，跳过。

 public String minRemoveToMakeValid(String s) {
    LinkedList<Integer> list=new LinkedList<>();
    for(int i=0;i<s.length();++i){
        char c=s.charAt(i);
        if(c=='('){
            list.addLast(i);
        } else if (c==')'){
            if(!list.isEmpty() && s.charAt(list.getLast())=='('){
                list.removeLast();
            } else {
                list.addLast(i);
            }
        } 
        
    }
    Iterator<Integer> it=list.iterator();
    if(!it.hasNext()) return s;
    int index=it.next();
    StringBuilder sb=new StringBuilder();
    for(int i=0;i<s.length();++i){
        if(i==index){
            if(it.hasNext()) index=it.next();
            continue;
        }
        sb.append(s.charAt(i));
    }
    return sb.toString();
}