How do you solve Minimum Remove to Make Valid Parentheses on LeetCode?

Minimum Remove to Make Valid Parentheses (LeetCode #1249) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Valid parentheses must have matching pairs.

What is the time complexity of Minimum Remove to Make Valid Parentheses?

The optimal solution for Minimum Remove to Make Valid Parentheses runs in O(n) time and uses O(n) space. The time complexity is O(n) because we traverse the string a constant number of times, and the space complexity is O(n) for storing the result.

What is the brute force solution for Minimum Remove to Make Valid Parentheses?

The brute force approach for Minimum Remove to Make Valid Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible combinations of the string by removing parentheses and checking if each combination is valid. This is simple but inefficient, especially for long strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Minimum Remove to Make Valid Parentheses?

Minimum Remove to Make Valid Parentheses uses the following concepts: String, Stack. The recommended patterns to study are: Two Pointers, Stack.

What are the interview tips for Minimum Remove to Make Valid Parentheses?

Explain your thought process clearly. Discuss edge cases before coding. Optimize your solution after the brute force approach.

What are common mistakes when solving Minimum Remove to Make Valid Parentheses?

Not counting unmatched parentheses correctly. Failing to handle edge cases like empty strings.

#1249

Minimum Remove to Make Valid Parentheses

Medium

StringStackTwo PointersStack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a two-pass approach to count and remove invalid parentheses. This is efficient because it only requires a single scan to count and another to build the valid string.

⚙️

Algorithm

2 steps

1Step 1: Count the number of unmatched '(' and ')' in the string.
2Step 2: Create a new string, adding characters only if they are valid (i.e., not exceeding the counts of '(' and ')').

solution.py22 lines

1def minRemoveToMakeValid(s):
2    open_count = 0
3    for char in s:
4        if char == '(': open_count += 1
5        elif char == ')':
6            if open_count > 0: open_count -= 1
7    close_count = 0
8    for char in s:
9        if char == ')': close_count += 1
10    result = []
11    for char in s:
12        if char == '(':
13            if open_count > 0:
14                result.append(char)
15                open_count -= 1
16        elif char == ')':
17            if close_count > 0:
18                result.append(char)
19                close_count -= 1
20        else:
21            result.append(char)
22    return ''.join(result)

ℹ

Complexity note: The time complexity is O(n) because we traverse the string a constant number of times, and the space complexity is O(n) for storing the result.

1Valid parentheses must have matching pairs.
2Counting unmatched parentheses helps in constructing the valid string.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.