Problem

In a Messenger-style text input, users may type strings containing letters and parentheses. Given a string s, remove the minimum number of parentheses so the resulting string is valid, and return the resulting string.

A string is valid if:

1. Every opening parenthesis '(' has a corresponding closing parenthesis ')'.
2. Parentheses are properly ordered.
3. Non-parenthesis characters remain unchanged.

Formal Specification

• Input: a string s
• Output: a string formed by removing the fewest parentheses from s so that it becomes valid

If multiple valid answers exist, return any one of them.

Examples

Example 1

• Input: s = "lee(t(c)o)de)"
• Output: "lee(t(c)o)de"
• Explanation: The final ')' is unmatched, so removing it yields a valid string.

Example 2

• Input: s = "a)b(c)d"
• Output: "ab(c)d"
• Explanation: The ')' after a has no matching '(', so it must be removed.

Example 3

• Input: s = "))(("
• Output: ""
• Explanation: No valid pairing is possible, so all parentheses are removed.

Constraints

• 1 <= len(s) <= 10^5
• s consists of lowercase English letters and the characters '(' and ')'
• Return any valid string with the minimum number of removals