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.Input Format
Input is managed for you
Output Format
Output is managed for you
Constraints
1: 1 <= s.length <= 10^5
2: s[i] is one of '(' , ')' and lowercase English letters.
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
a)b(c)d
Output
ab(c)d