Minimum Remove To Make Valid Parentheses - Leetcode Solution

Problem Statement:

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.

Solution:

To solve this problem, we can use a stack data structure to keep track of the opening parentheses '(' that we have encountered. Whenever we encounter a closing parentheses ')' and there is an opening parentheses at the top of the stack, we remove the opening parentheses from the stack and continue. If we encounter a closing parentheses and the stack is empty, we add this parentheses to a list of invalid parentheses indices.

After iterating through the entire string, we can remove all the parentheses at the indices in the list of invalid parentheses indices.

Here is the step-by-step algorithm:

1. Initialize a stack and a list to keep track of the invalid parentheses indices.

2. Iterate through the string s and for each character, do the following:

• If the character is an opening parentheses '(', push it onto the stack.
• If the character is a closing parentheses ')', and the stack is not empty, pop the opening parentheses from the top of the stack and continue.
• If the character is a closing parentheses ')' and the stack is empty, add the index of this parentheses to the list of invalid parentheses indices.
• If the character is neither an opening or closing parentheses, continue.

3. After iterating through the entire string, remove all the parentheses at the indices in the list of invalid parentheses indices.

4. Return the updated string.

Here is the implementation of the above algorithm in Python:

def minRemoveToMakeValid(s: str) -> str: stack = [] invalid_indices = []

for i, c in enumerate(s):
    if c == '(':
        stack.append(i)
    elif c == ')':
        if stack:
            stack.pop()
        else:
            invalid_indices.append(i)

# Add any remaining opening parentheses to the list of invalid indices
invalid_indices += stack

# Remove the invalid parentheses from the string
result = ''
for i, c in enumerate(s):
    if i not in invalid_indices:
        result += c

return result

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input string. This is because we iterate through the string once, and all the stack operations are constant time operations.

Space Complexity:

The space complexity of this algorithm is also O(n), where n is the length of the input string. This is because we use a stack and a list to keep track of the invalid parentheses indices, and the size of these data structures is proportional to the length of the input string.

1