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.