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 Insertions to Balance a Parentheses String

Difficulty: Medium

Problem Description

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'. You can insert the characters '(' and ')' at any position of the string to balance it if needed. Return the minimum number of insertions needed to make s balanced.

Key Insights

  • Each '(' requires two consecutive ')' to be balanced.
  • For every unmatched '(', we need to count how many ')' are missing.
  • Conversely, if there are extra ')' that do not have a matching '(', we need to account for how many '(' we need to add.
  • The approach needs to traverse the string while keeping track of the balance of parentheses.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a greedy algorithm. We'll iterate through the string, maintaining a counter for the balance of parentheses. For each character:

  • If we encounter a '(', we increment the balance.
  • If we encounter a ')', we check if the balance is greater than zero:
    • If it is, we decrement the balance (indicating a match).
    • If it is not, we need to add an opening parenthesis '(', so we increase the count of insertions needed.
  • At the end of the iteration, any unmatched '(' will require two ')' for each unmatched '('. Thus, we add double the balance to the count of insertions needed.

Code Solutions

def minInsertions(s: str) -> int:
    insertions = 0
    balance = 0
    
    i = 0
    while i < len(s):
        if s[i] == '(':
            balance += 1
            i += 1
        else:
            if i + 1 < len(s) and s[i + 1] == ')':
                # We have a matching '))'
                if balance > 0:
                    balance -= 1  # Match this with a '('
                else:
                    # Need to add a '(' for the unmatched '))'
                    insertions += 1
                i += 2
            else:
                # Only one ')' found, need to add another one and a '('
                if balance > 0:
                    balance -= 1  # Match with a '('
                else:
                    insertions += 1  # Need to add a '('
                insertions += 1  # We need another ')'
                i += 1

    # Each unmatched '(' needs two ')'
    insertions += balance * 2
    return insertions
← Back to All Questions