Minimum Remove To Make Valid Parentheses
medium
1: Given a string s of '(' , ')' and lowercase English characters 2: Your task is to remove the minimum number of parentheses ( '(' or ')') so that the resulting parentheses string is valid and return it. 3: In case of multiple valid strings give precedence in keeping innermost parenthesis. example (a(b(c)d) this string has (a(bc)d), (ab(c)d) and a(b(c)d) 3 valid strings. Among all 3 valid strings a(b(c)d) has the innermost parentheses.
Constraints
1: 1 <= s.length <= 10^5 2: s[i] is one of '(' , ')' and lowercase English letters.
Format
Input
Input is managed for you
Output
Output is managed for you
Example
Sample Input
a)b(c)d
Sample Output
ab(c)d