611. Minimum Remove to Make Valid Parentheses
You are given a string s made of lowercase English letters and the characters ( and ). Delete the minimum number of parentheses (letters always stay) so that what remains is valid: reading left to right, no ) ever appears without an unpaired ( before it, and every ( eventually gets closed.
Several different minimum deletion sets can exist, so the answer is pinned to one canonical choice: pair parentheses greedily left to right (each ) pairs with the nearest unpaired ( before it), then delete exactly the parentheses that end up unpaired — every ) that found nothing to close and every ( that was never closed. Return the resulting string; it may be empty.
Example 1:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: Both '(' pairs close correctly; the final ')' has nothing left to close, so it is the one deletion.
Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"
Explanation: The ')' after 'a' appears before any '(' and can never be matched — remove it. The (c) pair is fine.
Example 3:
Input: s = "))(("
Output: ""
Explanation: No ')' has an opener before it and no '(' has a closer after it, so all four characters must go.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters and the characters '(' and ')'.
Hints:
A ')' is doomed the moment it appears with no unpaired '(' to its left — no future character can save it. Track a counter of unpaired '(' while scanning.
The counter tells you *how many* '(' are left over but not *which ones*. Keep a stack of the indices of unpaired '(' instead; whatever is still on the stack at the end is exactly the set of '(' to delete, alongside the doomed ')' you marked during the scan.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "lee(t(c)o)de)"
Expected output: "lee(t(c)o)de"