Watch 10 video solutions for Minimum Remove to Make Valid Parentheses, a medium level problem involving String, Stack. This walkthrough by NeetCodeIO has 35,286 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
AB (A concatenated with B), where A and B are valid strings, or(A), where A is a valid string.
Example 1:
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:
Input: s = "a)b(c)d" Output: "ab(c)d"
Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105s[i] is either '(' , ')', or lowercase English letter.Problem Overview: You receive a string containing lowercase letters and parentheses. The goal is to remove the minimum number of characters so the remaining parentheses form a valid expression. A valid string means every opening ( has a matching closing ) in the correct order.
Approach 1: Two-Pass String Traversal with Index Tracking (Time: O(n), Space: O(n))
This method scans the string twice to filter invalid parentheses. During the first pass, iterate left to right and track the balance of open parentheses. Append characters to a temporary result but skip any closing parenthesis ) that does not have a matching open. This guarantees that the intermediate string never has excess closing brackets.
The second pass runs right to left to remove extra opening parentheses. Track remaining unmatched ( and skip them when building the final string. Using two passes ensures both imbalance cases are handled cleanly without complex bookkeeping. This approach relies purely on string traversal and counters, making it easy to implement when working with string processing problems.
Approach 2: Single-Pass Efficient Stack Solution (Time: O(n), Space: O(n))
The stack-based method records indices of unmatched parentheses while iterating once through the string. Push the index of every ( onto a stack. When encountering ), check the stack: if an opening parenthesis exists, pop it to form a valid pair; otherwise record the index of the invalid closing parenthesis.
After traversal, any remaining indices in the stack correspond to unmatched opening parentheses. Combine these with invalid closing indices and remove those positions from the string. The final string contains only valid pairs. This approach is common in parentheses validation problems because the stack directly models the nesting structure of expressions.
Recommended for interviews: The single-pass stack approach is the one most interviewers expect. It demonstrates clear understanding of parenthesis matching using a LIFO structure and maintains linear time complexity. The two-pass traversal is also strong because it avoids extra index bookkeeping and shows clean reasoning about invalid cases. Mentioning both approaches shows depth: one focuses on stack mechanics, the other on careful string filtering.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass String Traversal with Index Tracking | O(n) | O(n) | When you prefer simple logic using counters and sequential scans without managing a stack |
| Single-Pass Efficient Stack Solution | O(n) | O(n) | Best general approach for parenthesis validation and matching problems |