On a Meta surface such as Messenger, you are given a string s containing lowercase English letters plus the characters '(' and ')'. Remove the minimum number of parentheses so the resulting string is valid, and return the resulting string.
A parentheses string is valid if every opening parenthesis has a matching closing parenthesis in the correct order. Letters may appear anywhere and do not affect validity.
ss so that the result is validExample 1
s = "lee(t(c)o)de)""lee(t(c)o)de"')' makes the string valid.Example 2
s = "a)b(c)d""ab(c)d"')' after a is unmatched, so it must be removed.Example 3
s = "))(("""1 <= len(s) <= 10^5s[i] is either a lowercase English letter, '(', or ')'s = "lee(t(c)o)de)"Output"lee(t(c)o)de"WhyThe final `')'` is unmatched, so removing it yields a valid string.s = "a)b(c)d"Output"ab(c)d"WhyThe `')'` after `a` has no earlier `'('` to match, so it must be removed.s = "))(("Output""WhyNone of the parentheses can be matched, so all four characters are removed.1 <= s.length <= 10^5s[i] is a lowercase English letter, '(' , or ')'Return any valid string formed by removing the minimum number of parenthesesdef min_remove_to_make_valid(s):
