Make a Parentheses String Valid

Given a string `s` containing lowercase English letters and the characters `'('` and `')'`, remove the minimum number of parentheses so that the resulting string is valid. A string is considered valid if: - every `')'` has a matching `'('` before it, and - the total number of `'('` and `')'` is balanced. You must preserve the relative order of all remaining characters. Return **any** valid string that can be obtained after the minimum number of removals. Examples: - Input: `"lee(t(c)o)de)"` -> Output: `"lee(t(c)o)de"` - Input: `"a)b(c)d"` -> Output: `"ab(c)d"` - Input: `"))("` -> Output: `""` - Input: `"())()("` -> Output: `"()()"` or another valid minimum-removal result Possible follow-ups: 1. Return only the minimum number of removals. 2. If multiple optimal answers exist, return the lexicographically smallest valid result. 3. Discuss whether the extra space can be reduced.