Remove the Fewest Parentheses to Restore Validity

### Problem Remove as few parentheses as possible from s so the parentheses in the result are balanced: every prefix has at least as many opening as closing parentheses, and total counts agree. Lowercase letters stay in place and may not be removed. Return any result attaining the minimum number of removals; an empty or letters-only result is valid. ```cpp class Solution { public: string minRemoveToMakeValid(string s); }; ``` ### Examples **Example 1:** ```text Input: s = "(a))b(" Output: "(a)b" Explanation: Remove one excess closing parenthesis and the final unmatched opening parenthesis. Both removals are necessary. ``` **Example 2:** ```text Input: s = "a))(b(" Output: "ab" Explanation: Both closings precede every opening, so none can be matched; all four parentheses must be removed. ``` ### Constraints - The string has 1 to 100000 characters. - Every character is a parenthesis or lowercase English letter. ### Contract considerations An output may differ from the reference when several minimum-removal strings are valid. ```hint Read the boundary condition May letters be removed, and must a valid returned string also use the fewest parenthesis deletions? ``` ### What a Strong Answer Covers An output may differ from the reference when several minimum-removal strings are valid. ### Follow-up Questions Optional practice extension, separate from the original task: How could all distinct minimum-removal results be enumerated?