The title

1249. Remove invalid parentheses

You are given a string s composed of ‘(‘, ‘)’ and lowercase letters.

You need to remove the minimum number of ‘(‘ or ‘)’ (you can remove parentheses anywhere) from the string to make the rest of the ‘parenthesis string’ valid.

Please return any valid string.

A valid “parenthesis string” should meet any of the following requirements:

Empty strings or strings containing only lowercase letters can be written as strings AB (A concatenates B), where both A and B are valid “parenthesis strings” can be written as strings (A), where A is A valid “parenthesis string”

Example 1:

Input: s = "lee (t) (c) o DE)" output: "lee (t) (c) o DE" explanation: "lee (t (co) DE)", "lee (t (c) the ode)" is also a possible answer.Copy the code

Example 2:

Input: s = "a)b(c)d" output: "ab(c)d"Copy the code

Example 3:

Input: s = "))((" output: "" Explanation: Empty strings are also validCopy the code

Ideas:

This can be interpreted as an updated version of the valid parentheses, interspersing the parentheses with some characters, and then eventually not only returning true and false, but removing the least unreasonable parentheses.

The overall idea is the same as before, the core idea is to use the stack. Every time it encounters “(“, it pushes its subscript into the stack, and when it encounters “)”, it pushes out of the stack, but there is a little more logic here. Before it exits the stack, it must check whether the stack is empty or not. If so, it changes the “(” to “).

So go straight to the code:

/ * * *@param {string} s
 * @return {string}* /
var minRemoveToMakeValid = function(s) {
    let stack = [];
    let arr = s.split(' ');
    for(let i=0; i<arr.length; i++){if(arr[i] == '('){
            stack.push(i)
        }else if(arr[i] == ') ') {if(stack.length == 0){
                arr[i] = ' ';
            }else{
                stack.pop()
            }
        }
    }
    while(stack.length>0){
        arr[stack.pop()] = ' '
    }
    s = arr.join(' ');

    return s;
};
Copy the code