Problem Breakdown
Restatement: We are given a string containing lowercase letters and parentheses '(' / ')'. The goal is to delete the fewest number of characters (parentheses) such that the remaining sequence forms a valid parenthesis structure while preserving all other characters in their original relative order. A valid structure means every opening bracket has a matching closing bracket, properly nested.
Inputs:
- String (). Characters are
'(',')', or lowercase English letters.
Outputs:
- A string representing the result after minimum removals. Any valid configuration with minimal deletions is acceptable (e.g., if multiple pairs exist, removing either one might be fine as long as validity holds and count of removed parens is minimized).
Implicit Constraints & Edge Cases:
- Empty Output: If all parentheses must be removed to achieve validity (e.g., input
"))(("), the output should contain only letters if any exist, otherwise an empty string. The constraints allow length , but result can be effectively “empty” of parens. - No Parentheses: If no parentheses are present, it is already valid (remove count = 0).
- Nested Structures: Validity depends on nesting order
(A)(B)vs((AB)). We must respect the stack-based matching logic; we cannot simply remove any closing bracket if there’s an open one available earlier in the string without checking for proper closure later.
Intuition
Brute Force Approach (Insufficient): One might consider trying every possible subset of parentheses to keep, validating each candidate string ( check). With characters where roughly half are parens, this is exponential or at least combinatorial in complexity relative to the number of valid subsets. Even if we just try removing one by one and checking validity repeatedly, validation takes . Doing this for every removal candidate leads to a worst-case time complexity far exceeding typical limits ().
Key Insight:
A string is invalid only because it has “too many” closing parentheses relative to the available opening ones at that point in the scan (unmatched )), or too many opening parentheses remaining after all valid pairs are matched.
We can identify these specific characters greedily:
- Unmatched Closing Parentheses: Scanning left-to-right, if we encounter a
')'and there is no available'('to match it (balance count ), this')'must be removed. We cannot fix an unmatched closing parenthesis by removing something else; the only way to make that specific position valid is to delete that character or its matching open bracket from earlier, but since we want minimum removals and order matters, deleting the excess closer is optimal for local validity. - Unmatched Opening Parentheses: After handling all unmatched closing parentheses (conceptually), any remaining
'('in our tracking structure are those that were never closed by a')'. These must also be removed to satisfy balance requirements at the end of the string.
Optimal Strategy: Use a stack or counter approach during one pass to identify which specific indices correspond to invalid parentheses (either unmatched closing ones encountered early, or opening ones left over). Then construct the result by skipping those marked indices in a second conceptual step (or building directly while filtering). This ensures time complexity.
Approach
- Initialize Tracking Structures: Create an empty stack to store the indices of open parentheses
'('. Also, create a set or boolean arrayinvalid_indicesto mark characters that need removal. Using indices allows us to reconstruct the string later without modifying it in-place (since Python strings are immutable). - First Pass (Left-to-Right): Iterate through the input string with index :
- If character is
'(', push its index onto the stack. This represents an available open bracket waiting for a match. - If character is
')': Check if we have unmatched opens in our stack (stack not empty).- Match Found: Pop from stack. We found a valid pair, so both are kept conceptually.
- No Match: The current
)has no preceding open bracket to match it. Mark index as invalid for removal (invalid_indices.add(i)). Do not pop anything (stack remains empty or unchanged relative to this specific closing attempt).
- If character is a letter, ignore it in the stack logic but keep its position implicitly by iterating over original string later.
- If character is
- Handle Remaining Opens: After the loop finishes, any indices remaining on the stack represent
'('that were never closed (e.g., input(((). These are invalid and must be removed. Pop all remaining indices from the stack and add them toinvalid_indices. - Construct Result: Iterate through the original string again using index . If is not in
invalid_indices, append character to a result list/string builder. Join this list at the end to form the final valid string.
Complexity Analysis
- Time Complexity: . We iterate through the string twice (once for stack processing, once for building output). Stack operations (
push,pop) are amortized . Set lookups/insertions in Python average . Total linear time relative to input length. - Space Complexity: . We store indices of open parentheses on the stack (worst case all opens, e.g.,
((((), and we use a set/array for invalid markers which can also grow up to size in worst cases like))))). The result string construction requires space.
Solution
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
# Stack stores indices of unmatched open parentheses '('
stack = []
# Set to track indices that need removal (unmatched ')' or leftover '(')
invalid_indices = set()
for i, char in enumerate(s):
if char == '(':
# Push index of opening parenthesis onto stack
stack.append(i)
elif char == ')':
# If we have an open parenthesis to match this closing one
if stack:
stack.pop()
else:
# No matching '(' before this, mark ')' for removal
invalid_indices.add(i)
# Any remaining indices in the stack are unmatched opening parentheses
while stack:
idx = stack.pop()
invalid_indices.add(idx)
# Build result string by skipping marked indices to preserve order and content
res = []
for i, char in enumerate(s):
if i not in invalid_indices:
res.append(char)
return "".join(res)
Edge Cases Handled
- All Closing Parentheses (
))): The loop encounters)with empty stack. Both indices added toinvalid_indices. Result is an empty string (valid). - All Opening Parentheses (
((): Stack fills up. Loop ends. While-loop empties stack adding all open parens to removal set. Result preserves letters if any, otherwise empty of parens. - Mixed Characters: Letters are never added to
stackorinvalid_indices. They pass through the final construction loop unchanged as long as their index isn’t marked (which it won’t be). Order is preserved via iteration order in second pass. - Nested Structures (
(a(b)c)): Stack correctly tracks depth. Inner pairs match and pop, outer pair matches at end. No indices added to removal set unless structure is broken like(b).