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 Add to Make Parentheses Valid

Difficulty: Medium

Problem Description

Given a parentheses string s, you can insert a parenthesis at any position of the string. Your goal is to return the minimum number of moves required to make the parentheses string valid.

Key Insights

  • A valid parentheses string has matching opening and closing parentheses.
  • Each unmatched closing parenthesis requires an opening parenthesis to be added.
  • Each unmatched opening parenthesis requires a closing parenthesis to be added.
  • The total number of moves required is the sum of unmatched opening and closing parentheses.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as we are using a constant amount of space for counters.

Solution

To solve the problem, we can use two counters: one for unmatched opening parentheses and another for unmatched closing parentheses. We iterate through the string, updating these counters based on whether we encounter an opening or closing parenthesis. Finally, the result will be the sum of both counters, representing the minimum number of moves needed.

Code Solutions

def minAddToMakeValid(s: str) -> int:
    open_count = 0  # Counter for unmatched opening parentheses
    close_count = 0  # Counter for unmatched closing parentheses
    
    for char in s:
        if char == '(':
            open_count += 1  # Increment for an opening parenthesis
        else:
            if open_count > 0:
                open_count -= 1  # Match with an opening parenthesis
            else:
                close_count += 1  # Increment for an unmatched closing parenthesis
    
    return open_count + close_count  # Total moves needed
← Back to All Questions