LeetCode Solutions Blog

Minimum Remove to Make Valid Parentheses

Number: 1371

Difficulty: Medium

Paid? No

Problem Description

Given a string s consisting of lowercase English letters and parentheses ('(' and ')'), remove the minimum number of parentheses so that the resulting string becomes a valid parentheses string. A valid parentheses string is defined as one that either contains only lowercase characters or is formed by proper matching of parentheses.

Key Insights

Use a stack to record indices of unmatched '('.
Traverse the string once to identify unmatched ')' and push indices of '('.
Mark indices that need removal and reconstruct the valid string.
Greedy, one-pass validation is efficient.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(n) in the worst case for the stack and additional storage

Solution

We can solve the problem by iterating over the string with a stack to match parentheses:

For every character in the string:
- If the character is '(', push its index onto the stack.
- If it is ')', check if there is a matching '(' in the stack. If so, pop the top; otherwise, mark this index for removal.
After the iteration, any indices left in the stack (representing unmatched '(') should also be marked for removal.
Build the final string by skipping characters at marked indices. This approach ensures we only remove the minimum number of parentheses to achieve a valid string.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Define a function to remove invalid parentheses and return a valid string.
def minRemoveToMakeValid(s: str) -> str:
    # Initialize a list to store the indices of '(' that haven't been matched yet.
    open_stack = []
    # Use a set to record indices to remove.
    indices_to_remove = set()
    
    # Loop over every character and its index in the string.
    for i, char in enumerate(s):
        # If the character is an open parenthesis, store its index.
        if char == '(':
            open_stack.append(i)
        # If the character is a closing parenthesis.
        elif char == ')':
            # If there is a matching open parenthesis, pop from the stack.
            if open_stack:
                open_stack.pop()
            # Otherwise, mark the index of this unmatched ')' for removal.
            else:
                indices_to_remove.add(i)
    
    # Add any remaining unmatched '(' indices from the stack to the removal set.
    indices_to_remove = indices_to_remove.union(set(open_stack))
    
    # Build and return the valid string by skipping characters at indices to be removed.
    result = []
    for i, char in enumerate(s):
        if i not in indices_to_remove:
            result.append(char)
    return "".join(result)

# Example usage:
print(minRemoveToMakeValid("lee(t(c)o)de)"))