Jobs

Interviews

Discussions

Minimum Add to Make Parentheses Valid

Medium

Asked by:

More companies

26 views

Topics:

StringsStacksGreedy Algorithms

A parentheses string is valid if and only if:

It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

Constraints:

1 <= s.length <= 1000
s[i] is either '(' or ')'.

Try coding it in LeetCode

Minimum Add to Make Parentheses Valid

Medium

Asked by:

26 views

Topics:

StringsStacksGreedy Algorithms

A parentheses string is valid if and only if:

It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

Constraints:

1 <= s.length <= 1000
s[i] is either '(' or ')'.

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 is the maximum possible length of the input string s?
Can the input string s be empty or null?
Does the input string s contain any characters other than '(' and ')'?
If the string is already valid, should I return 0?
Are there any specific error conditions I should handle, such as a null or invalid input?

Brute Force Solution

Approach

The goal is to find the fewest parentheses we must add to a string of parentheses to make it balanced. The brute force way involves trying all combinations of adding parentheses until a valid arrangement is found, then selecting the best one.

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

Start by checking the original string to see if it's already valid. If so, we need to add zero parentheses.
If the original string is not valid, try adding a single left parenthesis at every possible position in the string and check if any of these new strings are valid.
Next, try adding a single right parenthesis at every possible position in the original string and check if any of these new strings are valid.
If none of those strings are valid, then try adding two parentheses. Start by adding two left parentheses in all possible combinations.
Then add one left and one right parenthesis in every possible combination.
Then add two right parentheses in every possible combination.
Check if any of the newly created strings are valid.
Continue adding more parentheses, exploring all combinations, until we find a valid string. Keep track of the number of parentheses added in each valid scenario.
Once a valid string is found, keep searching for strings that are also valid BUT require fewer added parentheses.
In the end, return the smallest number of additions it took to achieve a valid string.

Code Implementation

def minimum_add_to_make_parentheses_valid_brute_force(parentheses_string):
    minimum_additions_needed = float('inf')
    queue = [(parentheses_string, 0)]

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

        if is_valid(current_string):
            # We only want to keep track of the smallest additions
            minimum_additions_needed = min(minimum_additions_needed, additions_made)
            continue

        if additions_made >= minimum_additions_needed:
            continue

        # Try adding a left parenthesis at each position
        for index in range(len(current_string) + 1):
            new_string = current_string[:index] + '(' + current_string[index:]
            queue.append((new_string, additions_made + 1))

            # Limit the size of the queue
            if len(queue) > 1000:
                break

        # Try adding a right parenthesis at each position
        for index in range(len(current_string) + 1):
            new_string = current_string[:index] + ')' + current_string[index:]
            queue.append((new_string, additions_made + 1))

            # Limit the size of the queue
            if len(queue) > 1000:
                break

    return minimum_additions_needed

def is_valid(parentheses_string):
    balance = 0
    for char in parentheses_string:
        if char == '(': 
            balance += 1
        else:
            balance -= 1

        # String is invalid if the balance ever drops below 0
        if balance < 0:
            return False

    # The string is valid if the balance is 0 at the end
    return balance == 0

Big(O) Analysis

Time Complexity

O(infinity) – The described brute-force approach involves trying all possible combinations of adding parentheses until a valid string is found. In the worst-case scenario, if the original string is severely unbalanced or even contains no valid arrangement, the algorithm could potentially continue adding parentheses indefinitely, exploring an infinite search space. Even if we limit the maximum number of added parentheses, the number of combinations to explore grows exponentially. Therefore, the time complexity is effectively unbounded, or can be considered infinite in practical terms, as it lacks a defined upper limit tied to the input size n.

Space Complexity

O(N!) – The brute force solution described involves generating and checking all possible combinations of adding parentheses. In the worst-case scenario, where many parentheses need to be added, the number of possible combinations grows factorially with the number of parentheses added. To store these combinations of modified strings, a significant amount of memory is required, potentially leading to an auxiliary space usage proportional to N!, where N relates to the number of possible parenthesis insertion points and the number of parentheses that must be added. Furthermore, checking if each modified string is valid might involve using a stack, contributing O(N) space for each string checked, but the dominant factor remains the storage of generated combinations.

Optimal Solution

Approach

We need to figure out the fewest parentheses we need to add to a string so that every opening parenthesis has a matching closing one, and vice-versa. The key is to keep track of how many open parentheses are currently unmatched.

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

Start from the beginning of the string.
If you see an opening parenthesis, it needs a closing one eventually, so increase the count of unmatched open parentheses.
If you see a closing parenthesis, check if there are any unmatched open parentheses waiting for it.
If there are unmatched open parentheses, decrease the count because the closing parenthesis has found a match.
If there are NO unmatched open parentheses, then this closing parenthesis is extra and needs an opening parenthesis added before it, so increase the count of parentheses we need to add.
After checking the whole string, any remaining unmatched open parentheses will also need closing parentheses added, so add the count of those unmatched open parentheses to the total count of added parentheses.
The final count is the minimum number of parentheses that need to be added.

Code Implementation

def minAddToMakeValid(input_string):
    unmatched_open_parenthesis = 0
    needed_parenthesis_count = 0

    for character in input_string:
        if character == '(': 
            unmatched_open_parenthesis += 1

        elif character == ')':
            # If there is no open parenthesis
            # to match the current closing one.
            if unmatched_open_parenthesis == 0:
                needed_parenthesis_count += 1

            else:
                # Found matching parenthesis.
                unmatched_open_parenthesis -= 1

    # Add any remaining unmatched open
    # parenthesis to the result.
    needed_parenthesis_count += unmatched_open_parenthesis

    return needed_parenthesis_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once. For each character in the string of length n, it performs a constant number of operations: either incrementing or decrementing the open parenthesis count, or incrementing the number of additions needed. Therefore, the time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables to store the count of unmatched open parentheses and the count of parentheses to add. The space used by these variables remains constant regardless of the input string's length, which we can denote as N. No additional data structures such as arrays, lists, or hash maps are created. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return 0, as an empty string is already a valid parentheses string.
String with only opening parentheses: '((('	Count the number of unmatched opening parentheses and return that count.
String with only closing parentheses: ')))'	Count the number of unmatched closing parentheses and return that count.
String with alternating parentheses: '()()()'	Return 0, as the string is already valid.
String with mixed but invalid parentheses: '())('	Keep track of the balance; unmatched closing parens add to answer and unmatched opening parens at the end also added.
Very long string consisting only of '(' to test for stack overflow	Iterative approach using a counter avoids stack overflow issues.
String with deeply nested valid parentheses followed by invalid close parentheses: '((((()))))'	The counter-based approach handles the nesting and correctly counts remaining unmatched close parenthesis after the valid sequence.
String with a mix of extremely unbalanced open and close parenthesis '((((((())))))(('	The algorithm correctly handles accumulation of unmatched open and close parentheses.

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 is the maximum possible length of the input string s?
Can the input string s be empty or null?
Does the input string s contain any characters other than '(' and ')'?
If the string is already valid, should I return 0?
Are there any specific error conditions I should handle, such as a null or invalid input?

Brute Force Solution

Approach

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

Start by checking the original string to see if it's already valid. If so, we need to add zero parentheses.
If the original string is not valid, try adding a single left parenthesis at every possible position in the string and check if any of these new strings are valid.
Next, try adding a single right parenthesis at every possible position in the original string and check if any of these new strings are valid.
If none of those strings are valid, then try adding two parentheses. Start by adding two left parentheses in all possible combinations.
Then add one left and one right parenthesis in every possible combination.
Then add two right parentheses in every possible combination.
Check if any of the newly created strings are valid.
Continue adding more parentheses, exploring all combinations, until we find a valid string. Keep track of the number of parentheses added in each valid scenario.
Once a valid string is found, keep searching for strings that are also valid BUT require fewer added parentheses.
In the end, return the smallest number of additions it took to achieve a valid string.

Code Implementation

def minimum_add_to_make_parentheses_valid_brute_force(parentheses_string):
    minimum_additions_needed = float('inf')
    queue = [(parentheses_string, 0)]

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

        if is_valid(current_string):
            # We only want to keep track of the smallest additions
            minimum_additions_needed = min(minimum_additions_needed, additions_made)
            continue

        if additions_made >= minimum_additions_needed:
            continue

        # Try adding a left parenthesis at each position
        for index in range(len(current_string) + 1):
            new_string = current_string[:index] + '(' + current_string[index:]
            queue.append((new_string, additions_made + 1))

            # Limit the size of the queue
            if len(queue) > 1000:
                break

        # Try adding a right parenthesis at each position
        for index in range(len(current_string) + 1):
            new_string = current_string[:index] + ')' + current_string[index:]
            queue.append((new_string, additions_made + 1))

            # Limit the size of the queue
            if len(queue) > 1000:
                break

    return minimum_additions_needed

def is_valid(parentheses_string):
    balance = 0
    for char in parentheses_string:
        if char == '(': 
            balance += 1
        else:
            balance -= 1

        # String is invalid if the balance ever drops below 0
        if balance < 0:
            return False

    # The string is valid if the balance is 0 at the end
    return balance == 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start from the beginning of the string.
If you see an opening parenthesis, it needs a closing one eventually, so increase the count of unmatched open parentheses.
If you see a closing parenthesis, check if there are any unmatched open parentheses waiting for it.
If there are unmatched open parentheses, decrease the count because the closing parenthesis has found a match.
If there are NO unmatched open parentheses, then this closing parenthesis is extra and needs an opening parenthesis added before it, so increase the count of parentheses we need to add.
After checking the whole string, any remaining unmatched open parentheses will also need closing parentheses added, so add the count of those unmatched open parentheses to the total count of added parentheses.
The final count is the minimum number of parentheses that need to be added.

Code Implementation

def minAddToMakeValid(input_string):
    unmatched_open_parenthesis = 0
    needed_parenthesis_count = 0

    for character in input_string:
        if character == '(': 
            unmatched_open_parenthesis += 1

        elif character == ')':
            # If there is no open parenthesis
            # to match the current closing one.
            if unmatched_open_parenthesis == 0:
                needed_parenthesis_count += 1

            else:
                # Found matching parenthesis.
                unmatched_open_parenthesis -= 1

    # Add any remaining unmatched open
    # parenthesis to the result.
    needed_parenthesis_count += unmatched_open_parenthesis

    return needed_parenthesis_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return 0, as an empty string is already a valid parentheses string.
String with only opening parentheses: '((('	Count the number of unmatched opening parentheses and return that count.
String with only closing parentheses: ')))'	Count the number of unmatched closing parentheses and return that count.
String with alternating parentheses: '()()()'	Return 0, as the string is already valid.
String with mixed but invalid parentheses: '())('	Keep track of the balance; unmatched closing parens add to answer and unmatched opening parens at the end also added.
Very long string consisting only of '(' to test for stack overflow	Iterative approach using a counter avoids stack overflow issues.
String with deeply nested valid parentheses followed by invalid close parentheses: '((((()))))'	The counter-based approach handles the nesting and correctly counts remaining unmatched close parenthesis after the valid sequence.
String with a mix of extremely unbalanced open and close parenthesis '((((((())))))(('	The algorithm correctly handles accumulation of unmatched open and close parentheses.