Minimum Remove to Make Valid Parentheses - Solution & Explanation
Problem Statement
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:
- It is the empty string, contains only lowercase characters, or
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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.
Approach Overview
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 1: Two-Pass String Traversal with Index Tracking
This approach involves performing two passes over the string. In the first pass, traverse the string to identify unmatched closing parentheses and their indices. In the second pass, traverse from right to left to identify unmatched opening parentheses. This process allows removing these indices to yield a balanced parentheses string.
An array is used to filter out invalid closing parentheses on the first pass. The second pass corrects the string from the right by ignoring invalid opening parens, then reverses the string to final form.
Complexity
Time Complexity: O(n), where n is the length of the string, since each character is visited once in each pass.
Space Complexity: O(n), as we potentially have to store the valid portion of the string.
Approach 2: Single-Pass Efficient Stack Solution
This strategy employs a single-pass solution with a stack to track the indices of unmatched parentheses. Upon completing the pass, these tracked indices inform which characters can remain in the final valid string output. This approach saves memory by avoiding additional passes over the string.
The C implementation uses an integer stack to track the positions of parentheses. It marks invalid parentheses with a dot character and subsequently uses a secondary pass to construct the valid string.
Complexity
Time Complexity: O(n), since each position in the strings is evaluated at most twice.
Space Complexity: O(n) for the indices stored during parentheses checking.
Approach 3: Two Passes
First, we scan from left to right and remove the extra right parentheses. Then, we scan from right to left and remove the extra left parentheses.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Similar problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pass String Traversal with Index Tracking | Time Complexity: O(n), where n is the length of the string, since each character is visited once in each pass. |
| Single-Pass Efficient Stack Solution | Time Complexity: O(n), since each position in the strings is evaluated at most twice. |
| Two Passes | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Remove to Make Valid Parentheses - Leetcode 1249 - Python • NeetCodeIO • 36,334 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Remove to Make Valid Parentheses easy or hard?
Minimum Remove to Make Valid Parentheses Python/Java solution
How to solve Minimum Remove to Make Valid Parentheses in O(n)?
What is the best approach for Minimum Remove to Make Valid Parentheses?
Is Minimum Remove to Make Valid Parentheses asked at Google/Amazon/Meta?
What data structure is used in Minimum Remove to Make Valid Parentheses?
What is the time complexity of Minimum Remove to Make Valid Parentheses?
Ready to solve this problem?
Practice Minimum Remove to Make Valid Parentheses with our built-in code editor and test cases.
Practice on FleetCode