Minimum Remove to Make Valid Parentheses

Given a string s of lowercase English letters and parentheses, remove the minimum number of parentheses (either '(' or ')', in any positions) so that the resulting parentheses string is valid. We define an empty string as valid. Output the minimum number of removals and the final valid string. Example Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Input: s = "a)b(c)d" Output: "ab(c)d" Input: s = "))((" Output: "" Constraints 1 <= s.length <= 10^5 s[i] can be either '(', ')' or lowercase English letters Example Input lee(t(c)o)de)