Jobs

Interviews

Discussions

Minimum Remove to Make Valid Parentheses

Medium

Minimum Remove to Make Valid Parentheses

Medium

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 length of the input string s?
Can the input string s be empty or null?
If there are multiple valid results (strings with the minimum number of removals), is any one acceptable, or is there a specific one I should return (e.g., the one that removes characters at the earliest indices)?
Are the only characters allowed in the string '(' , ')' and lowercase English letters, or can there be other characters?
Is the returned string expected to maintain the original relative order of the valid parentheses and other characters, or is rearranging them acceptable?

Brute Force Solution

Approach

The brute force method for making parentheses valid involves trying every possible combination of removals. We explore all possibilities by removing different parentheses one by one until we find a valid combination.

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

Consider every possible combination of parentheses that could be removed from the original string.
For each combination, create a new string with only the parentheses that were not removed.
Check if the new string has valid parentheses – meaning, for every open parenthesis, there's a corresponding closing parenthesis in the correct order.
If the string is valid, compare its length with the lengths of other valid strings you've found so far.
Keep track of the longest valid string you find by going through all the combinations.
After checking every possible combination, return the longest valid string.

Code Implementation

def minimum_remove_to_make_valid_parentheses_brute_force(input_string):
    longest_valid_string = ""

    # Generate all possible substrings by removing characters
    for i in range(1 << len(input_string)):
        current_string = ""
        indices_to_keep = []

        for j in range(len(input_string)):
            if (i >> j) & 1:
                current_string += input_string[j]
                indices_to_keep.append(j)

        # Check if the current string is valid
        if is_valid(current_string):

            # We want to keep the longest one found so far
            if len(current_string) > len(longest_valid_string):
                longest_valid_string = current_string

    return longest_valid_string

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

            # If balance becomes negative, it's invalid
            if balance < 0:
                return False
    # String is valid if balance is 0
    return balance == 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach involves generating every possible subset of the input string of length n. There are 2^n such subsets. For each subset, we need to check if the parentheses are valid. Checking validity requires iterating through the subset which takes O(n) time in the worst case (the subset has all n characters). Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(2^N) – The brute force approach generates all possible combinations of removals. Each combination can be represented as a string, and in the worst case, there could be 2^N combinations (where N is the length of the input string) as each character can be either kept or removed. Storing all these combinations in memory results in a space complexity that is exponential with respect to the input size. Additionally, the recursion stack for generating combinations can grow up to a depth of N, contributing O(N) space, which is dominated by the exponential term.

Optimal Solution

Approach

The key idea is to scan the input once to identify and mark the parentheses that need to be removed to make the string valid. We use a counter to keep track of open parentheses and then remove the extra ones that don't have a match.

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

Go through the string from left to right.
Keep track of how many opening parentheses you've seen.
When you see a closing parenthesis, check if you have an opening parenthesis to match it with.
If you do have a match, decrease the count of open parentheses because one opening parenthesis has now been matched.
If you *don't* have a match, that means you have an extra closing parenthesis that needs to be removed.
Now, go through the string from right to left.
Keep track of how many closing parentheses you've seen.
When you see an opening parenthesis, check if you have a closing parenthesis to match it with.
If you do have a match, decrease the count of closing parentheses.
If you *don't* have a match, that means you have an extra opening parenthesis that needs to be removed.
Finally, build a new string containing only the characters that weren't marked for removal.

Code Implementation

def min_remove_to_make_valid(input_string: str) -> str:
    string_length = len(input_string)
    indices_to_remove = [False] * string_length
    open_parenthesis_count = 0

    for index in range(string_length):
        if input_string[index] == '(': 
            open_parenthesis_count += 1
        elif input_string[index] == ')':
            if open_parenthesis_count > 0:
                open_parenthesis_count -= 1
            else:
                # Mark extra closing parenthesis for removal.
                indices_to_remove[index] = True

    closing_parenthesis_count = 0

    for index in range(string_length - 1, -1, -1):
        if input_string[index] == ')':
            closing_parenthesis_count += 1
        elif input_string[index] == '(': 
            if closing_parenthesis_count > 0:
                closing_parenthesis_count -= 1
            else:
                # Mark extra opening parenthesis for removal.
                indices_to_remove[index] = True

    result = ''
    for index in range(string_length):
        if not indices_to_remove[index]:
            result += input_string[index]

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves three main steps: iterating through the string from left to right, iterating through the string from right to left, and building the final string. Each of these iterations processes each character in the input string once. Therefore, the time complexity is directly proportional to the length of the input string, n, resulting in O(n) time complexity.

Space Complexity

–

Edge Cases

Case	How to Handle
Empty string input	Return the empty string itself, as it's already a valid parentheses string of length 0.
String with only opening parentheses	Remove all opening parentheses to get an empty valid string.
String with only closing parentheses	Remove all closing parentheses to get an empty valid string.
String with balanced parentheses and other characters	The solution correctly identifies and preserves the balanced parentheses and other characters.
String with nested unbalanced parentheses	The algorithm efficiently removes only the necessary unbalanced parentheses.
String with a large number of characters	The solution should have a time complexity of at most O(n) to handle large inputs efficiently, where n is the length of the string.
String with deeply nested parentheses that could potentially cause stack overflow issues if recursion were used inappropriately	Iterative solutions should be preferred to avoid potential stack overflow for deeply nested parentheses; Stack based solution should bound memory appropriately.
String with mixed valid and invalid parentheses scattered throughout	The solution should maintain the relative order of valid parentheses and non-parenthesis characters while removing the minimum number of invalid 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 length of the input string s?
Can the input string s be empty or null?
If there are multiple valid results (strings with the minimum number of removals), is any one acceptable, or is there a specific one I should return (e.g., the one that removes characters at the earliest indices)?
Are the only characters allowed in the string '(' , ')' and lowercase English letters, or can there be other characters?
Is the returned string expected to maintain the original relative order of the valid parentheses and other characters, or is rearranging them acceptable?

Brute Force Solution

Approach

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

Consider every possible combination of parentheses that could be removed from the original string.
For each combination, create a new string with only the parentheses that were not removed.
Check if the new string has valid parentheses – meaning, for every open parenthesis, there's a corresponding closing parenthesis in the correct order.
If the string is valid, compare its length with the lengths of other valid strings you've found so far.
Keep track of the longest valid string you find by going through all the combinations.
After checking every possible combination, return the longest valid string.

Code Implementation

def minimum_remove_to_make_valid_parentheses_brute_force(input_string):
    longest_valid_string = ""

    # Generate all possible substrings by removing characters
    for i in range(1 << len(input_string)):
        current_string = ""
        indices_to_keep = []

        for j in range(len(input_string)):
            if (i >> j) & 1:
                current_string += input_string[j]
                indices_to_keep.append(j)

        # Check if the current string is valid
        if is_valid(current_string):

            # We want to keep the longest one found so far
            if len(current_string) > len(longest_valid_string):
                longest_valid_string = current_string

    return longest_valid_string

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

            # If balance becomes negative, it's invalid
            if balance < 0:
                return False
    # String is valid if balance is 0
    return balance == 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the string from left to right.
Keep track of how many opening parentheses you've seen.
When you see a closing parenthesis, check if you have an opening parenthesis to match it with.
If you do have a match, decrease the count of open parentheses because one opening parenthesis has now been matched.
If you *don't* have a match, that means you have an extra closing parenthesis that needs to be removed.
Now, go through the string from right to left.
Keep track of how many closing parentheses you've seen.
When you see an opening parenthesis, check if you have a closing parenthesis to match it with.
If you do have a match, decrease the count of closing parentheses.
If you *don't* have a match, that means you have an extra opening parenthesis that needs to be removed.
Finally, build a new string containing only the characters that weren't marked for removal.

Code Implementation

def min_remove_to_make_valid(input_string: str) -> str:
    string_length = len(input_string)
    indices_to_remove = [False] * string_length
    open_parenthesis_count = 0

    for index in range(string_length):
        if input_string[index] == '(': 
            open_parenthesis_count += 1
        elif input_string[index] == ')':
            if open_parenthesis_count > 0:
                open_parenthesis_count -= 1
            else:
                # Mark extra closing parenthesis for removal.
                indices_to_remove[index] = True

    closing_parenthesis_count = 0

    for index in range(string_length - 1, -1, -1):
        if input_string[index] == ')':
            closing_parenthesis_count += 1
        elif input_string[index] == '(': 
            if closing_parenthesis_count > 0:
                closing_parenthesis_count -= 1
            else:
                # Mark extra opening parenthesis for removal.
                indices_to_remove[index] = True

    result = ''
    for index in range(string_length):
        if not indices_to_remove[index]:
            result += input_string[index]

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

–

Edge Cases

Case	How to Handle
Empty string input	Return the empty string itself, as it's already a valid parentheses string of length 0.
String with only opening parentheses	Remove all opening parentheses to get an empty valid string.
String with only closing parentheses	Remove all closing parentheses to get an empty valid string.
String with balanced parentheses and other characters	The solution correctly identifies and preserves the balanced parentheses and other characters.
String with nested unbalanced parentheses	The algorithm efficiently removes only the necessary unbalanced parentheses.
String with a large number of characters	The solution should have a time complexity of at most O(n) to handle large inputs efficiently, where n is the length of the string.
String with deeply nested parentheses that could potentially cause stack overflow issues if recursion were used inappropriately	Iterative solutions should be preferred to avoid potential stack overflow for deeply nested parentheses; Stack based solution should bound memory appropriately.
String with mixed valid and invalid parentheses scattered throughout	The solution should maintain the relative order of valid parentheses and non-parenthesis characters while removing the minimum number of invalid parentheses.