Minimum Remove to Make Valid Parentheses

Given a string s 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.

Example 1:

Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d" Output: "ab(c)d"

Example 3:

Input: s = "))((" Output: "" Explanation: An empty string is also valid.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '(' , ')', or lowercase English letter.

class Solution:
    def minRemoveToMakeValid(self, 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)

        # Remaining indices in the stack are unmatched '('
        indices_to_remove.update(stack)

        result = []
        for i, char in enumerate(s):
            if i not in indices_to_remove:
                result.append(char)

        return "".join(result)

Naive Approach

The naive approach would be to generate all possible subsequences of the string s and check each one for validity. Then return the valid string with the longest length. This approach is not efficient since the number of subsequences of a string of length n is 2^n. This results in exponential time complexity, which is not practical for larger input sizes.

Optimal Approach

The optimal approach involves using a stack to keep track of the indices of open parentheses. When a closing parenthesis is encountered, check if there's a corresponding open parenthesis in the stack. If there is, pop the open parenthesis from the stack. If not, or if there are unmatched open parentheses in the stack after processing the entire string, mark those parentheses for removal. Finally, construct a new string excluding those marked for removal.

Example

Consider the input string s = "lee(t(c)o)de)".

1. Iterate through the string.
2. When you see '(', push its index to the stack.
3. When you see ')', check if the stack is non-empty.
   • If the stack is non-empty, pop from the stack.
   • If the stack is empty, mark the index of ')' to be removed.
4. After iteration, any remaining indices in the stack are also marked to be removed.
5. Build the final string by skipping the marked indices.

Big O Analysis

Time Complexity

The time complexity of the provided solution is O(n), where n is the length of the input string s. This is because the algorithm iterates through the string once to identify the indices to remove and then iterates through the string again to construct the result. Both iterations take O(n) time, so the overall time complexity is O(n).

Space Complexity

The space complexity of the provided solution is O(n) in the worst case. This is because the stack can grow up to the number of open parentheses in the string s, and indices_to_remove can also store up to n indices in the worst case (e.g., "((((((("). Additionally, the result list can grow up to n characters. Thus, the overall space complexity is O(n).

Edge Cases

1. Empty String: If the input string s is empty, the function should return an empty string. The provided code handles this case correctly since the loops will not execute, and the initial empty string will be returned.
2. String with no parentheses: If the string s contains no parentheses, it is already a valid parentheses string, so the function should return the original string. The provided code handles this case correctly because the stack and indices_to_remove will remain empty, and the result will be the same as the input string.
3. String with only open parentheses: If the string s contains only open parentheses, all the indices should be removed. The provided code handles this case correctly because after the loop, the stack will contain all the indices, and they will be added to indices_to_remove.
4. String with only close parentheses: If the string s contains only close parentheses, all the indices should be removed. The provided code handles this case correctly because the stack will always be empty, and the index of each close parenthesis will be added to indices_to_remove.
5. String with nested parentheses: The code correctly handles nested parentheses by pushing and popping from the stack appropriately.
6. Very long strings: The algorithm has a linear time complexity of O(n), making it efficient even for very long strings (up to the constraint length of 10^5).