Minimum Remove to Make Valid Parentheses

Problem Given a string of lowercase letters and parentheses, remove the minimum number of parentheses (at any positions) so the resulting string is valid. Return any valid result.

Input / Output

• Input: string s of '(' , ')' and lowercase letters.
• Output: a valid string after minimal removals.

Constraints

• 1 ≤ s.length ≤ 10^5
• s contains only lowercase letters, '(' and ')'.

Example

• s="a)b(c)d" -> "ab(c)d"
• s="))((" -> ""
• s="lee(t(c)o)de" -> "lee(t(c)o)de"