1249. Minimum Remove to Make Valid Parentheses

Обновлено: 2024-04-15

1 мин

Algorithms , LeetCode

Содержание

LeetCode problem 1249

Approach

The problem can be solved in two passes using a stack for the first pass and a simple iteration for the second:

First Pass (Identify Invalid Parentheses):

Iterate through the string, and for every character:
- If it’s ‘(’, push its index onto the stack.
- If it’s ‘)’ and the stack is not empty (there is a matching ‘(’), pop from the stack. Otherwise, mark this ‘)’ as invalid.
After the iteration, any indices remaining in the stack represent unmatched ‘(’ that should be removed.

Second Pass (Build the Result String):

Iterate through the string again, building the result string by including characters that are not marked as invalid.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []                      # Stack to keep track of the indices of '('
        remove_indices = set()          # Set to keep track of indices to remove

        for i, char in enumerate(s):    # First pass to identify invalid parentheses
            if char == '(':
                stack.append(i)
            elif char == ')':
                if stack:
                    stack.pop()
                else:
                    remove_indices.add(i)
                    
        # Add indices of remaining '(' to remove
        remove_indices = remove_indices.union(set(stack))
        
        # Second pass to build the result string
        result = [s[i] for i in range(len(s)) if i not in remove_indices]
        
        return ''.join(result)