Minimum Removal to Make Valid Parentheses String

meta Given a string s of '(' , ')' and lowercase English characters, your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and returns any valid string. A string is valid if it has balanced parentheses. Test cases: Input: "lee(t(c)o)de)" Output: "lee(t(c)o)de" Input: "a)b(c)d" Output: "ab(c)d" Input: "))(" Output: "" Input: "(a(b(c)d)" Output: "a(b(c)d)" Assume 0 <= s.length <= 10^4. Example Input lee(t(c)o)de)