In a Messenger-style text input, users may type strings containing letters and parentheses. Given a string s, remove the minimum number of parentheses so the resulting string is valid, and return the resulting string.
A string is valid if:
'(' has a corresponding closing parenthesis ')'.ss so that it becomes validIf multiple valid answers exist, return any one of them.
Example 1
s = "lee(t(c)o)de)""lee(t(c)o)de"')' is unmatched, so removing it yields a valid string.Example 2
s = "a)b(c)d""ab(c)d"')' after a has no matching '(', so it must be removed.Example 3
s = "))(("""1 <= len(s) <= 10^5s consists of lowercase English letters and the characters '(' and ')'s = "lee(t(c)o)de)"Output"lee(t(c)o)de"WhyThe last closing parenthesis is unmatched, so removing it produces a valid string.s = "a)b(c)d"Output"ab(c)d"WhyThe closing parenthesis after `a` has no matching opening parenthesis and must be removed.s = "))(("Output""WhyAll parentheses are unmatched, so the minimum valid result is the empty string.1 <= s.length <= 10^5s consists of lowercase English letters and the characters '(' and ')'Any valid string with the minimum number of removals is acceptabledef min_remove_to_make_valid(s):
