Minimum Insertions to Balance a Parentheses String

Medium

Asked by:

57 views

Topics:

StringsGreedy Algorithms

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 '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

In other words, we treat '(' as an opening parenthesis and '))' as a closing parenthesis.

For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.

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.

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Constraints:

1 <= s.length <= 10⁵
s consists of '(' and ')' only.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can the input string contain other than '(' and ')'?
Can the input string be empty or null?
If the string is already balanced, should I return 0?
Are there any length constraints on the input string?
Is there a specific approach you'd prefer me to use, or are you open to me choosing the most efficient one?

Brute Force Solution

Approach

The brute force approach to balancing a parentheses string is like trying every possible combination of inserting open and close parentheses until we find one that works. It involves exploring every possible alteration to the string and verifying its balance.

Here's how the algorithm would work step-by-step:

Start with the original parentheses string.
Try inserting an open or close parenthesis at every possible position within the string.
For each new string you create, check if it's balanced. A balanced string means that for every open parenthesis, there's a matching close parenthesis in the correct order.
If a string isn't balanced, discard it and try inserting parentheses at different positions or different types of parentheses.
If a string is balanced, remember how many insertions it took to create it.
Repeat this process of inserting and checking until you've explored all reasonable possibilities, or perhaps up to some maximum number of insertions.
From all the balanced strings you found, pick the one that required the fewest insertions. That's your answer.

Code Implementation

def minimum_insertions_brute_force(parentheses_string):
    min_insertions = float('inf')
    queue = [(parentheses_string, 0)]

    while queue:
        current_string, insertions = queue.pop(0)

        # Check if the current string is balanced
        if is_balanced(current_string):
            min_insertions = min(min_insertions, insertions)
            continue

        if insertions >= min_insertions:
            continue

        # Limit search depth to avoid infinite loops
        if insertions > len(parentheses_string):
            continue

        for index in range(len(current_string) + 1):
            # Try inserting an open parenthesis
            new_string_open = current_string[:index] + '(' + current_string[index:]
            queue.append((new_string_open, insertions + 1))

            # Try inserting a close parenthesis
            new_string_close = current_string[:index] + ')' + current_string[index:]
            queue.append((new_string_close, insertions + 1))

    if min_insertions == float('inf'):
        return -1

    return min_insertions

def is_balanced(parentheses_string):
    balance = 0

    for char in parentheses_string:
        if char == '(': balance += 1
        elif char == ')': balance -= 1

        #Early exit if unbalanced
        if balance < 0: return False

    #After processing the entire string, it is balanced if the balance is zero
    return balance == 0

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores inserting parentheses at every possible position in the string. For a string of length n, there are n+1 possible insertion points. At each point, we can insert either an open or a close parenthesis, doubling the possibilities. This exponential growth in the number of possible strings to check leads to a time complexity of O(2^(2n)), which simplifies to O(2^n). The string balancing check may contribute O(n) operations per string, but the exponential factor dominates overall.

Space Complexity

O(N!) – The brute force approach attempts every possible combination of inserting open or close parentheses. In the worst case, the algorithm might need to explore strings with a large number of insertions, potentially leading to a tree-like structure of explored strings in memory. Each level of this tree represents a different insertion, and the number of branches grows factorially with the number of possible insertion positions. Therefore, the space complexity is approximately O(N!), where N indirectly represents the maximum number of insertions explored, as each insertion leads to storing a new string variant. While not explicitly stored, the conceptual space usage involved in exploring string combinations corresponds to O(N!).

Optimal Solution

Approach

The key is to keep track of how many open parentheses we need to close. We also need to recognize that two closing parentheses are always required for every open parenthesis. We address imbalances as they appear, ensuring that we only add insertions when absolutely necessary.

Here's how the algorithm would work step-by-step:

Go through the string from left to right, one character at a time.
If you see an open parenthesis, increase the number of closing parentheses that are needed later.
If you see a closing parenthesis, check if you already need a closing parenthesis. If you don't, you'll need to insert an open parenthesis before this one.
After potentially handling the open parenthesis insertion, determine if there are enough immediate closing parenthesis to fulfill its requirement. If not, insert a closing parenthesis.
Continue this process until you reach the end of the string.
Finally, if there are any remaining closing parentheses needed, add them to the end.
The total number of open and closing parentheses you inserted is the answer.

Code Implementation

def min_insertions(parenthesis_string):
    needed_closing_parentheses = 0
    insertions = 0

    for character in parenthesis_string:
        if character == '(': 
            needed_closing_parentheses += 2

        elif character == ')':
            # We need to insert an opening parenthesis.
            if needed_closing_parentheses == 0:
                insertions += 1
                needed_closing_parentheses = 1

            # Reduce the need for a closing parenthesis.
            needed_closing_parentheses -= 1

    # Any remaining needed closing parenthesis at the end need insertions.
    insertions += needed_closing_parentheses

    return insertions

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input string of length n exactly once, performing a constant number of operations (checking character type, incrementing/decrementing counters, and potentially inserting parentheses) for each character. No nested loops or recursive calls are involved. Therefore, the time complexity is directly proportional to the length of the string. The operations scale linearly with the input size, thus resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm described in the plain English explanation primarily utilizes a fixed number of integer variables to keep track of the count of needed closing parentheses and the number of insertions. No auxiliary data structures like arrays, lists, or hash maps are used to store intermediate results or track visited states. Therefore, the amount of extra memory used by the algorithm remains constant irrespective of the length of the input string N, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately since an empty string is already balanced.
Input string with only opening parentheses	The number of insertions needed is twice the number of opening parentheses.
Input string with only closing parentheses	The number of insertions needed is the number of closing parentheses.
String with deeply nested parentheses	Stack-based or counter-based approaches must handle large nesting depths without overflow.
String with unbalanced parentheses at the end	The algorithm should correctly account for any remaining unmatched parentheses after processing the entire string.
Maximum length string with highly unbalanced parentheses	The solution's time and space complexity should be considered to ensure it scales efficiently.
Input string with mixed single and double closing parenthesis	The solution should be able to differentiate '(' from ')' and ')))'.
String starts with single close parenthesis	Add an open parenthesis to the total insertion and consider the string '(...' for future balancing.

Null or empty input string

How to Handle:

Return 0 immediately since an empty string is already balanced.

Input string with only opening parentheses

How to Handle:

The number of insertions needed is twice the number of opening parentheses.

Input string with only closing parentheses

How to Handle:

The number of insertions needed is the number of closing parentheses.

String with deeply nested parentheses

How to Handle:

Stack-based or counter-based approaches must handle large nesting depths without overflow.

String with unbalanced parentheses at the end

How to Handle:

The algorithm should correctly account for any remaining unmatched parentheses after processing the entire string.

Maximum length string with highly unbalanced parentheses

How to Handle:

The solution's time and space complexity should be considered to ensure it scales efficiently.

Input string with mixed single and double closing parenthesis

How to Handle:

The solution should be able to differentiate '(' from ')' and ')))'.

String starts with single close parenthesis

How to Handle:

Add an open parenthesis to the total insertion and consider the string '(...' for future balancing.