We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Remove to Make Valid Parentheses

Difficulty: Medium

Problem Description

Given a string s of '(', ')', and lowercase English characters, your task is to remove the minimum number of parentheses (either '(' or ')') in any positions so that the resulting parentheses string is valid and return any valid string.

Key Insights

  • A valid parentheses string must have matching opening and closing parentheses.
  • The problem can be solved using a stack to keep track of unmatched parentheses.
  • We can iterate through the string to count unmatched parentheses and then create a new valid string by skipping invalid ones.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We iterate through the string a couple of times. Space Complexity: O(n), in the worst case, where we store the result in a list.

Solution

To solve the problem, we can use a two-pass approach:

  1. In the first pass, we count the number of unmatched '(' and ')' parentheses.
  2. In the second pass, we construct the resulting valid string by including only the valid parentheses and all other characters.

We can utilize a stack data structure to help in the validation of parentheses and keep track of their indices.

Code Solutions

def minRemoveToMakeValid(s: str) -> str:
    # First pass: Count unmatched parentheses
    open_count = 0
    close_count = 0
    for char in s:
        if char == '(':
            open_count += 1
        elif char == ')':
            if open_count > 0:
                open_count -= 1
            else:
                close_count += 1

    # Second pass: Build the result
    result = []
    for char in s:
        if char == '(' and open_count > 0:
            open_count -= 1
            continue
        if char == ')' and close_count > 0:
            close_count -= 1
            continue
        result.append(char)

    return ''.join(result)
← Back to All Questions