Minimum Remove to Make Valid Parentheses

Medium

Apple

2 views

Topics:

StringsStacksTwo Pointers

Given a string s consisting of '(', ')' and lowercase English characters, your task is to remove the minimum number of parentheses ('(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
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.

For example:

Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" (or "lee(t(co)de)" or "lee(t(c)ode)") would also be accepted.
Input: s = "a)b(c)d" Output: "ab(c)d"
Input: s = "))((" Output: ""

Write an algorithm to solve this problem efficiently. Explain the time and space complexity of your solution. Also, what are some edge cases you considered in your solution?

Minimum Remove to Make Valid Parentheses

Medium

Apple

2 views

Topics:

StringsStacksTwo Pointers

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
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.

For example:

Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" (or "lee(t(co)de)" or "lee(t(c)ode)") would also be accepted.
Input: s = "a)b(c)d" Output: "ab(c)d"
Input: s = "))((" Output: ""

Write an algorithm to solve this problem efficiently. Explain the time and space complexity of your solution. Also, what are some edge cases you considered in your solution?

Solution

Naive Approach: Brute Force

The most straightforward approach is to generate all possible subsequences of the given string by either keeping or removing each parenthesis. Then, check if each subsequence is a valid parentheses string. We keep the valid string of maximal length. If several valid strings have the same maximal length, any of them can be returned.

This approach is highly inefficient due to the exponential number of possible subsequences (2^n, where n is the length of the string).

Time Complexity: O(2^n * n), where n is the length of the string.
Space Complexity: O(n), primarily due to the recursion depth.

Optimal Approach: Using a Stack (or Counter)

A more efficient approach involves using a stack (or a counter) to keep track of open parentheses. We iterate through the string, and for each character, we perform the following:

If it's an open parenthesis '(', push it onto the stack (or increment the counter).
If it's a close parenthesis ')', check if the stack is empty (or counter is zero). If it is, this parenthesis needs to be removed. If it's not, pop from the stack (or decrement the counter).
If it's a character, we keep it.

After the first iteration, we will know which closing parentheses to remove. However, we might still have unmatched opening parentheses in the stack (or a counter value that's not zero). In a second iteration, we eliminate the extra opening parentheses from our constructed string.

Edge Cases

Empty String: Should return an empty string.
No Parentheses: Should return the original string.
Only Opening Parentheses: Should return an empty string.
Only Closing Parentheses: Should return an empty string.
Unbalanced Parentheses (e.g., "a)b(c)d"): Should remove the minimum number of parentheses to make it valid.

Code (Python)

def min_remove_to_make_valid(s: str) -> str:
    stack = []
    indices_to_remove = set()

    for i, char in enumerate(s):
        if char == '(':        
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                indices_to_remove.add(i)

    while stack:
        indices_to_remove.add(stack.pop())

    result = ""
    for i, char in enumerate(s):
        if i not in indices_to_remove:
            result += char

    return result

Time Complexity: O(n), where n is the length of the string, as we iterate through the string at most twice.
Space Complexity: O(n) in the worst case, if the stack (or counter) stores almost all the indices of the string.

Solution

Naive Approach: Brute Force

This approach is highly inefficient due to the exponential number of possible subsequences (2^n, where n is the length of the string).

Time Complexity: O(2^n * n), where n is the length of the string.
Space Complexity: O(n), primarily due to the recursion depth.

Optimal Approach: Using a Stack (or Counter)

A more efficient approach involves using a stack (or a counter) to keep track of open parentheses. We iterate through the string, and for each character, we perform the following:

If it's an open parenthesis '(', push it onto the stack (or increment the counter).
If it's a close parenthesis ')', check if the stack is empty (or counter is zero). If it is, this parenthesis needs to be removed. If it's not, pop from the stack (or decrement the counter).
If it's a character, we keep it.

Edge Cases

Empty String: Should return an empty string.
No Parentheses: Should return the original string.
Only Opening Parentheses: Should return an empty string.
Only Closing Parentheses: Should return an empty string.
Unbalanced Parentheses (e.g., "a)b(c)d"): Should remove the minimum number of parentheses to make it valid.

Code (Python)

def min_remove_to_make_valid(s: str) -> str:
    stack = []
    indices_to_remove = set()

    for i, char in enumerate(s):
        if char == '(':        
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                indices_to_remove.add(i)

    while stack:
        indices_to_remove.add(stack.pop())

    result = ""
    for i, char in enumerate(s):
        if i not in indices_to_remove:
            result += char

    return result

Time Complexity: O(n), where n is the length of the string, as we iterate through the string at most twice.
Space Complexity: O(n) in the worst case, if the stack (or counter) stores almost all the indices of the string.