Minimum Parentheses Removal

A string that contains correctly ordered parenthesis (), is a valid parenthesis string. More specifically, it must meet the following conditions:

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

Given a string s, consisting of parenthesis and lowercase English characters. Remove the minimum number of parentheses ( '(' or ')' ) to make the resulting parentheses string valid. Multiple valid strings may be possible, but since minimum removal operations are performed, there will be only one correct answer.

For example, consider the following string as input:

s = "alg(o(d)a)il)y"

All parenthesis are valid except the last one. Removing it will give alg(o(d)a)ily which is the correct answer. alg(o(da)il)y or alg(o(d)ail)y could also be correct answers, but they require more operations, and hence only alg(o(d)a)ily is valid.

Note: this problem is similar to Remove Invalid Parentheses, with the difference being that we only want the smallest valid result.

Constraints

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.