Problem

On a Meta surface such as Messenger, you are given a string s containing lowercase English letters plus the characters '(' and ')'. Remove the minimum number of parentheses so the resulting string is valid, and return the resulting string.

A parentheses string is valid if every opening parenthesis has a matching closing parenthesis in the correct order. Letters may appear anywhere and do not affect validity.

Formal Specification

• Input: a string s
• Output: a string formed by removing the fewest parentheses from s so that the result is 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: Removing the last ')' makes the string valid.

Example 2

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

Example 3

• Input: s = "))(("
• Output: ""
• Explanation: No parentheses can be matched, so all must be removed.

Constraints

• 1 <= len(s) <= 10^5
• s[i] is either a lowercase English letter, '(', or ')'
• The solution must remove the minimum number of parentheses