Loading problem…
Given a string s of '(' , ')' and lowercase English characters, remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. 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: Remove the trailing unmatched ')'.
Example 2
Input: s = a)b(c)d
Output: ab(c)d
Explanation: The ')' at index 1 has no '(' before it to match, so it is removed. The remaining "(c)" is balanced, giving "ab(c)d".
Example 3
Input: s = ))((
Output:
Explanation: The two ')' come before any '(' and the two '(' are never closed, so all four must be removed, leaving an empty string.
Scan once. Push each '(' index onto a stack; on a ')', pop a match or mark this ')' for removal. Any '(' left on the stack at the end is also unmatched.
Run checks all cases above. Submit evaluates all test cases.