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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Insertions to Balance a Parentheses String

Number: 1648

Difficulty: Medium

Paid? No

Companies: Meta, Google, TikTok, Amazon, J.P. Morgan

Problem Description

Given a string s consisting only of '(' and ')', balance the string by ensuring every '(' has a matching pair of consecutive '))'. You are allowed to insert '(' or ')' anywhere in the string. The task is to determine the minimum number of insertions required to make the string balanced.

Key Insights

  • Every '(' expects exactly two ')' to be balanced.
  • Process the string with a single pass, maintaining the count of required ')' characters.
  • When encountering a ')', check if it forms a consecutive pair. If not, a missing ')' may need to be inserted.
  • If extra ')' are found without a matching '(', insert a '('.
  • Greedily handle the unmatched parentheses while iterating through the string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s as we traverse the string once.
Space Complexity: O(1), using only a few integer variables for counting.

Solution

We use a greedy approach with a counter (needed) that indicates how many ')' characters are required to balance the string so far. As we iterate:

  1. When a '(' is encountered, increment the needed count by 2.
  2. When a ')' is encountered:
    • If it is the start of a pair, decrement the needed count by 2.
    • If a single ')' is encountered (i.e., the next character is not ')' or we are at the end), we assume one is missing and adjust the counter accordingly (and count an insertion).
  3. If needed becomes negative at any point, it means there are extra ')' so we insert a '(' and adjust.
  4. At the end, any remaining needed value implies missing ')' which are added as insertions.

Key tricks:

  • Ensure that when a needed count goes negative, we immediately fix it by inserting a '('.
  • Carefully check pairs of consecutive ')' to determine if they form valid closing pairs.

Code Solutions

# Python solution with line-by-line comments

def minInsertions(s: str) -> int:
    insertions = 0        # to count total insertions required
    needed = 0            # needed number of ')' to balance the string
    i = 0                 # pointer to traverse the string

    while i < len(s):
        # If current char is '(' then add two needed ')'
        if s[i] == '(':
            needed += 2
            # If needed becomes odd, insert one ) immediately
            if needed % 2 != 0:
                insertions += 1
                needed -= 1  # fix imbalance by assuming insertion of extra ')'
        else:
            # If current char is ')'
            needed -= 1  # one ')' satisfies part of a needed pair

            # Check if next char exists and forms a pair
            if i+1 < len(s) and s[i+1] == ')':
                i += 1  # skip the next ')' as it forms a proper consecutive pair
            else:
                # single ')' encountered, so insert one more ')'
                insertions += 1
                needed -= 1

            # If needed becomes negative, that means there is an extra ')' 
            if needed < 0:
                insertions += 1  # insert '(' to balance extra ')'
                needed += 2     # after insertion, 2 ')' are needed
        i += 1

    return insertions + needed  # remaining needed ')' count as insertions

# Example usage:
print(minInsertions("(()))"))
print(minInsertions("())"))
print(minInsertions("))())("))
← Back to All Questions