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.

**Example 4**:

Input: s = “(a(b(c)d)”

Output: “a(b(c)d)”

Initial thought was do a BFS search where each outgoing node is the string without a bracket. At any level if we find a solution, we stop there (for e.g. in below example we would stop at Level 1 itself since we find “ab(c)d”).

"a)b(c)d" "ab(c)d" ✔️ "a)bc)d" "a)b(cd" "abc)d" "ab(cd" ... ... |

However, above solution will time out.

Instead we use the stack data structure to determine the brackets that cause invalidity of parentheses. These are simply the brackets remaining in the stack (at the end of validity test). With the bracket, we also store the index of the bracket (in the string) which makes it quicker to delete characters from those positions and rebuild valid string.

/** * @param {string} s * @return {string} */ // Node representing bracket and its index (in the string) var Node = function(c, idx) { this.c = c; this.idx = idx; } var minRemoveToMakeValid = function(s) { let sChars = Array.from(s); // Use a stack to determine which brackets are causing 'invalidity' // We use Node data strcuture so that we know its index's (which makes it easy to remove) let stk = []; for ( let i = 0 ; i < sChars.length ; i++ ) { let curr = new Node(sChars[i], i); if ( curr.c === '(' || (curr.c === ')' && stk.length === 0) ) { stk.push(curr); } else if ( curr.c === ')' ) { let prev = stk.pop(); if ( prev.c === ')' ) { stk.push(prev); stk.push(curr); } } } // index'es which we need to remove let toDelete = stk.map(function(n) { return n.idx; }); // build new string! let newS = ''; for ( let i = 0 ; i < sChars.length ; i++ ) { if (toDelete.includes(i)) continue; newS += sChars[i]; } return newS; }; |