Minimum Remove to Make Valid Parentheses
Asked at Meta
Problem
Given a string containing lowercase English letters, parentheses, and possibly other characters, remove the minimum number of invalid parentheses to make the input string valid. Return any valid result.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | MEDIUM | View all Meta questions → |
How to Think About It
Brute force: generate all subsets of characters and check validity — O(2^n).
Use a stack to track unmatched opening parentheses as you scan left to right.
Mark indices of unmatched parentheses for removal.
First pass: find unmatched '(' by counting open > close. Second pass: remove excess '(' from the right.
Combine both passes: remove unmatched '(' and unmatched ')' in a single string construction.
Optimal Approach
Perform two passes. First pass: scan left to right, tracking open count. Any ')' that appears when open is zero is marked for removal. After the first pass, any remaining open count means we have unmatched '(' — mark the rightmost unmatched '(' for removal. Build the result string by skipping marked indices. This runs in O(n) time with O(n) space.
What Trips People Up in Real Interviews
Clarify that non-parenthesis characters should always be kept.
Edge case: empty string returns empty string.
Edge case: no parentheses at all returns the original string.
Walk through "lee(t(c)o)de)" to show both removals.
Mention two-pass approach: first remove unmatched ')', then unmatched '('.
Solution Code
def minRemoveToMakeValid(s: str) -> str:
indices_to_remove = set()
open_count = 0
for i, ch in enumerate(s):
if ch == '(':
open_count += 1
elif ch == ')':
if open_count == 0:
indices_to_remove.add(i)
else:
open_count -= 1
stack = []
for i, ch in enumerate(s):
if ch == '(' and open_count > 0:
open_count -= 1
continue
if i not in indices_to_remove:
stack.append(ch)
return ''.join(stack)Frequently Asked Questions
What is the Minimum Remove to Make Valid Parentheses problem?
Given a string containing lowercase English letters, parentheses, and possibly other characters, remove the minimum number of invalid parentheses to make the input string valid. Return any valid result.
How do you solve Minimum Remove to Make Valid Parentheses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Remove to Make Valid Parentheses?
Minimum Remove to Make Valid Parentheses is asked at Meta. It is a medium difficulty problem.
What are common mistakes on Minimum Remove to Make Valid Parentheses?
- Clarify that non-parenthesis characters should always be kept.
- Edge case: empty string returns empty string.
- Edge case: no parentheses at all returns the original string.
- Walk through "lee(t(c)o)de)" to show both removals.
- Mention two-pass approach: first remove unmatched ')', then unmatched '('.