Minimum Remove to Make Valid Parentheses

Naive Solution: Brute Force

One straightforward, albeit inefficient, approach is to generate all possible subsequences of the input string s and check each subsequence for validity. We would keep track of the longest valid subsequence found so far. This involves exploring all possible combinations of including or excluding each character, leading to exponential time complexity.

Algorithm:

1. Generate all subsequences of the input string.
2. For each subsequence, check if it's a valid parentheses string.
3. If a subsequence is valid, compare its length with the length of the longest valid subsequence found so far. Update if necessary.
4. Return the longest valid subsequence.

Validity Check:

A string is a valid parentheses string if:

• It's empty.
• It contains only lowercase characters.
• The number of opening parentheses equals the number of closing parentheses, and for every closing parenthesis, there exists a corresponding opening parenthesis to its left.

Code (Python): Brute Force (Illustrative - Not Optimized)

def is_valid(s):
    balance = 0
    for char in s:
        if char == '(': 
            balance += 1
        elif char == ')':
            balance -= 1
            if balance < 0:
                return False
    return balance == 0

def remove_invalid_parentheses_brute_force(s):
    import itertools

    all_subsequences = []
    for i in range(len(s) + 1):
        for subset in itertools.combinations(s, i):
            all_subsequences.append("".join(subset))

    valid_subsequences = [sub for sub in all_subsequences if is_valid(sub)]

    if not valid_subsequences:
      return ""

    return max(valid_subsequences, key=len)

#Example usage:
s = "lee(t(c)o)de)"
result = remove_invalid_parentheses_brute_force(s)
print(result)

Big O Analysis (Brute Force):

• Time Complexity: O(2ⁿ * n), where n is the length of the input string. Generating all subsequences takes O(2ⁿ) time, and checking the validity of each subsequence takes O(n) time.
• Space Complexity: O(n), primarily due to storing the subsequences and recursion depth.

Optimal Solution: Using Stack and Two Passes

A more efficient approach involves using a stack (or a counter) to keep track of parentheses balance and performing two passes through the string.

Algorithm:

1. First Pass (Left to Right):
   • Iterate through the string from left to right.
   • Maintain a balance counter. Increment for '(' and decrement for ')'.
   • If balance becomes negative, it means there are more closing parentheses than opening parentheses. Mark the current ')' for removal. Reset balance to 0.
2. Second Pass (Right to Left):
   • Iterate through the string from right to left.
   • Maintain a balance counter. Increment for ')' and decrement for '('.
   • If balance becomes negative, it means there are more opening parentheses than closing parentheses. Mark the current '(' for removal. Reset balance to 0.
3. Build the Result: Construct a new string by excluding the characters marked for removal.

Code (Python):

def remove_invalid_parentheses(s):
    s_list = list(s)
    
    def remove_invalid(s_list, char1, char2):
        balance = 0
        for i in range(len(s_list)):            
            if s_list[i] == char1:
                balance += 1
            elif s_list[i] == char2:
                balance -= 1
            
            if balance < 0:
                s_list[i] = ""
                balance = 0
        return s_list

    # First pass: Remove extra ')'
    s_list = remove_invalid(s_list, '(', ')')
    
    # Reverse the string and remove extra '('
s_list.reverse()
    s_list = remove_invalid(s_list, ')', '(')
    s_list.reverse()

    return "".join(s_list)

#Example usage:
s = "lee(t(c)o)de)"
result = remove_invalid_parentheses(s)
print(result)

s = "a)b(c)d"
result = remove_invalid_parentheses(s)
print(result)

s = "))(("
result = remove_invalid_parentheses(s)
print(result)

Edge Cases:

• Empty string: Should return an empty string.
• String with only valid parentheses and characters: Should return the original string.
• String with only invalid parentheses: Should return an empty string or a valid string after removing parentheses.

Big O Analysis (Optimal):

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string a maximum of three times.
• Space Complexity: O(n) in the worst case, to store the list representation of the string. In some cases, it might be O(1) if you can modify the string in-place, but this is not recommended in most languages due to immutability of strings.