Make Parentheses String Valid with Minimum Removals

Given a string s consisting of lowercase letters and parentheses '(' and ')', remove the minimum number of parentheses so that the resulting string has valid parentheses. A valid parentheses string means: Every '(' must be matched with a ')' that comes after it. Every ')' must be matched with a '(' that comes before it. Return any valid result. Constraints: 1 <= len(s) <= 1e5 Requirements: O(n) time and O(n) (or better) space. Examples: Input: "a)b(c)d" Output: "ab(c)d" Input: "))(" Output: "" Example Input a)b(c)d Output ab(c)d