Remove Invalid Parentheses

Given a string s, remove the minimum number of parentheses to make s valid. Return all possible results.

Note: A valid string has balanced parentheses (every opening parenthesis has a matching closing parenthesis).

Example(s)

Example 1:

Input: s = "(()()()"
Output: ["()()()","(())()","(()())"]
Explanation:
The string has 4 opening and 3 closing parentheses.
We need to remove 1 opening parenthesis.
Removing at different positions gives different valid strings.

Example 2:

Input: s = "()()()"
Output: ["()()()"]
Explanation:
The string is already valid, so no removals needed.

Example 3:

Input: s = "()())()"
Output: ["()()()", "(())()"]
Explanation:
We need to remove 1 closing parenthesis.
Removing the first ')' at index 2 or the second ')' at index 3.

Example 4:

Input: s = "(a)())()"
Output: ["(a)()()", "(a())()"]
Explanation:
We need to remove 1 closing parenthesis.

Solution

The solution uses backtracking with two passes:

First pass: Count unmatched opening parentheses (need to remove some '(')
Second pass: Count unmatched closing parentheses (need to remove some ')')
Backtracking: Generate all combinations of removing the unmatched parentheses
Validation: Check if the resulting string is valid
Deduplication: Use a set to avoid duplicate results

JavaScript Solution
Python Solution

JavaScript Solution

/**
* Remove minimum parentheses to make string valid
* @param {string} s - Input string
* @return {string[]} - All possible valid strings
*/
function removeInvalidParentheses(s) {
const result = new Set();

// Count how many '(' and ')' we need to remove
let leftRem = 0;  // Unmatched opening parentheses
let rightRem = 0;  // Unmatched closing parentheses

// First pass: count unmatched opening parentheses
for (let char of s) {
  if (char === '(') {
    leftRem++;
  } else if (char === ')') {
    if (leftRem > 0) {
      leftRem--;  // Matched
    } else {
      rightRem++;  // Unmatched
    }
  }
}

/**
 * Backtracking function to generate all valid strings
 * @param {string} str - Current string being built
 * @param {number} index - Current index in original string
 * @param {number} leftCount - Number of '(' used so far
 * @param {number} rightCount - Number of ')' used so far
 * @param {number} leftRem - Remaining '(' to remove
 * @param {number} rightRem - Remaining ')' to remove
 */
function backtrack(str, index, leftCount, rightCount, leftRem, rightRem) {
  // Base case: processed entire string
  if (index === s.length) {
    // Valid if balanced and no more removals needed
    if (leftRem === 0 && rightRem === 0 && leftCount === rightCount) {
      result.add(str);
    }
    return;
  }
  
  const char = s[index];
  
  // Case 1: Skip this character (remove it)
  if ((char === '(' && leftRem > 0) || (char === ')' && rightRem > 0)) {
    backtrack(
      str,
      index + 1,
      leftCount,
      rightCount,
      leftRem - (char === '(' ? 1 : 0),
      rightRem - (char === ')' ? 1 : 0)
    );
  }
  
  // Case 2: Keep this character
  if (char !== '(' && char !== ')') {
    // Regular character, always keep
    backtrack(str + char, index + 1, leftCount, rightCount, leftRem, rightRem);
  } else if (char === '(') {
    // Opening parenthesis
    backtrack(str + char, index + 1, leftCount + 1, rightCount, leftRem, rightRem);
  } else if (char === ')' && rightCount < leftCount) {
    // Closing parenthesis (only if we have matching opening)
    backtrack(str + char, index + 1, leftCount, rightCount + 1, leftRem, rightRem);
  }
}

backtrack('', 0, 0, 0, leftRem, rightRem);
return Array.from(result);
}

// Test cases
console.log('Example 1:', removeInvalidParentheses("(()()()")); 
// ["()()()","(())()","(()())"]

console.log('Example 2:', removeInvalidParentheses("()()()")); 
// ["()()()"]

console.log('Example 3:', removeInvalidParentheses("()())()")); 
// ["()()()", "(())()"]

console.log('Example 4:', removeInvalidParentheses("(a)())()")); 
// ["(a)()()", "(a())()"]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

from typing import List, Set

def remove_invalid_parentheses(s: str) -> List[str]:
  """
  Remove minimum parentheses to make string valid
  
  Args:
      s: Input string
      
  Returns:
      List[str]: All possible valid strings
  """
  result: Set[str] = set()
  
  # Count how many '(' and ')' we need to remove
  left_rem = 0  # Unmatched opening parentheses
  right_rem = 0  # Unmatched closing parentheses
  
  # First pass: count unmatched opening parentheses
  for char in s:
      if char == '(':
          left_rem += 1
      elif char == ')':
          if left_rem > 0:
              left_rem -= 1  # Matched
          else:
              right_rem += 1  # Unmatched
  
  def backtrack(
      current: str,
      index: int,
      left_count: int,
      right_count: int,
      left_rem: int,
      right_rem: int
  ):
      """
      Backtracking function to generate all valid strings
      """
      # Base case: processed entire string
      if index == len(s):
          # Valid if balanced and no more removals needed
          if left_rem == 0 and right_rem == 0 and left_count == right_count:
              result.add(current)
          return
      
      char = s[index]
      
      # Case 1: Skip this character (remove it)
      if (char == '(' and left_rem > 0) or (char == ')' and right_rem > 0):
          backtrack(
              current,
              index + 1,
              left_count,
              right_count,
              left_rem - (1 if char == '(' else 0),
              right_rem - (1 if char == ')' else 0)
          )
      
      # Case 2: Keep this character
      if char != '(' and char != ')':
          # Regular character, always keep
          backtrack(current + char, index + 1, left_count, right_count, left_rem, right_rem)
      elif char == '(':
          # Opening parenthesis
          backtrack(current + char, index + 1, left_count + 1, right_count, left_rem, right_rem)
      elif char == ')' and right_count < left_count:
          # Closing parenthesis (only if we have matching opening)
          backtrack(current + char, index + 1, left_count, right_count + 1, left_rem, right_rem)
  
  backtrack('', 0, 0, 0, left_rem, right_rem)
  return list(result)

# Test cases
print('Example 1:', sorted(remove_invalid_parentheses("(()()()")))  
# ['()()()', '(()())', '(())()']

print('Example 2:', remove_invalid_parentheses("()()()"))  
# ['()()()']

print('Example 3:', sorted(remove_invalid_parentheses("()())()")))  
# ['()()()', '(())()']

print('Example 4:', sorted(remove_invalid_parentheses("(a)())()")))  
# ['(a)()()', '(a())()']

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Optimized with Pruning)

Here's an optimized version with better pruning:

JavaScript Optimized
Python Optimized

/**
 * Optimized version with better pruning
 */
function removeInvalidParenthesesOptimized(s) {
  const result = new Set();
  
  // Count removals needed
  let leftRem = 0, rightRem = 0;
  for (let char of s) {
    if (char === '(') leftRem++;
    else if (char === ')') {
      if (leftRem > 0) leftRem--;
      else rightRem++;
    }
  }
  
  function isValid(str) {
    let count = 0;
    for (let char of str) {
      if (char === '(') count++;
      else if (char === ')') {
        count--;
        if (count < 0) return false;
      }
    }
    return count === 0;
  }
  
  function backtrack(str, index, leftRem, rightRem, open) {
    if (leftRem < 0 || rightRem < 0 || open < 0) return;
    
    if (index === s.length) {
      if (leftRem === 0 && rightRem === 0 && isValid(str)) {
        result.add(str);
      }
      return;
    }
    
    const char = s[index];
    
    if (char === '(') {
      // Remove this '('
      if (leftRem > 0) {
        backtrack(str, index + 1, leftRem - 1, rightRem, open);
      }
      // Keep this '('
      backtrack(str + char, index + 1, leftRem, rightRem, open + 1);
    } else if (char === ')') {
      // Remove this ')'
      if (rightRem > 0) {
        backtrack(str, index + 1, leftRem, rightRem - 1, open);
      }
      // Keep this ')' (only if we have open '(')
      if (open > 0) {
        backtrack(str + char, index + 1, leftRem, rightRem, open - 1);
      }
    } else {
      // Regular character, always keep
      backtrack(str + char, index + 1, leftRem, rightRem, open);
    }
  }
  
  backtrack('', 0, leftRem, rightRem, 0);
  return Array.from(result);
}

def remove_invalid_parentheses_optimized(s: str) -> List[str]:
    """
    Optimized version with better pruning
    """
    result: Set[str] = set()
    
    # Count removals needed
    left_rem = right_rem = 0
    for char in s:
        if char == '(':
            left_rem += 1
        elif char == ')':
            if left_rem > 0:
                left_rem -= 1
            else:
                right_rem += 1
    
    def is_valid(str_val: str) -> bool:
        count = 0
        for char in str_val:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0
    
    def backtrack(current: str, index: int, left_rem: int, right_rem: int, open_count: int):
        if left_rem < 0 or right_rem < 0 or open_count < 0:
            return
        
        if index == len(s):
            if left_rem == 0 and right_rem == 0 and is_valid(current):
                result.add(current)
            return
        
        char = s[index]
        
        if char == '(':
            # Remove this '('
            if left_rem > 0:
                backtrack(current, index + 1, left_rem - 1, right_rem, open_count)
            # Keep this '('
            backtrack(current + char, index + 1, left_rem, right_rem, open_count + 1)
        elif char == ')':
            # Remove this ')'
            if right_rem > 0:
                backtrack(current, index + 1, left_rem, right_rem - 1, open_count)
            # Keep this ')' (only if we have open '(')
            if open_count > 0:
                backtrack(current + char, index + 1, left_rem, right_rem, open_count - 1)
        else:
            # Regular character, always keep
            backtrack(current + char, index + 1, left_rem, right_rem, open_count)
    
    backtrack('', 0, left_rem, right_rem, 0)
    return list(result)

Complexity

Time Complexity: O(2^n) in the worst case, where n is the length of the string. However, with pruning, it's typically much better in practice.
Space Complexity: O(n) for the recursion stack, plus O(k) where k is the number of valid results.

Approach

The solution uses backtracking with two phases:

Count phase: Determine how many '(' and ')' need to be removed
- Count unmatched opening parentheses
- Count unmatched closing parentheses
Backtracking phase: Generate all combinations
- For each character, decide whether to keep or remove it
- Prune invalid branches early
- Track balance of parentheses
- Collect valid results
Key optimizations:
- Only remove the minimum number needed
- Skip consecutive duplicates to avoid duplicate results
- Early pruning when balance becomes negative

Key Insights

Two-pass counting: First determine what needs to be removed
Backtracking: Generate all combinations of removals
Pruning: Early termination of invalid branches
Deduplication: Use a set to avoid duplicate results
Balance tracking: Ensure parentheses remain balanced during construction

Step-by-Step Example

Let's trace through Example 1: s = "(()()()"

Step 1: Count removals needed
  s = "(()()()"
  leftRem = 0, rightRem = 0
  Process: '(' → leftRem=1
           '(' → leftRem=2
           ')' → leftRem=1
           '(' → leftRem=2
           ')' → leftRem=1
           '(' → leftRem=2
           ')' → leftRem=1
  Result: leftRem=1, rightRem=0 (need to remove 1 '(')

Step 2: Backtracking
  Try removing '(' at different positions:
  - Remove index 0: "()()()" ✓
  - Remove index 1: "()()()" (duplicate)
  - Remove index 3: "(())()" ✓
  - Remove index 5: "(()())" ✓

Result: ["()()()","(())()","(()())"]

Edge Cases

Already valid: Return the original string
All opening: Remove all opening parentheses
All closing: Remove all closing parentheses
Empty string: Return [""]
No parentheses: Return the original string
Consecutive duplicates: Handle carefully to avoid duplicate results

Optimization: Skip Consecutive Duplicates

To avoid duplicate results when there are consecutive identical parentheses:

// In backtrack function, add this check:
if (index > 0 && s[index] === s[index - 1]) {
  // Skip if we already tried removing this character
  // (when previous character was also removed)
}

Valid Parentheses: Check if parentheses are balanced
Generate Parentheses: Generate all valid parentheses combinations
Longest Valid Parentheses: Find longest valid substring
Minimum Remove to Make Valid: Return just one valid string (simpler)

Takeaways

Backtracking is powerful for generating all combinations
Two-phase approach (count then generate) is efficient
Pruning is crucial for performance
Deduplication is important when generating all results
Balance tracking ensures we maintain valid parentheses throughout

Example(s)​

Solution​

JavaScript Solution

Output:

Python Solution

Output:

Alternative Solution (Optimized with Pruning)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Edge Cases​

Optimization: Skip Consecutive Duplicates​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Optimized with Pruning)

Complexity

Approach

Key Insights

Step-by-Step Example

Edge Cases

Optimization: Skip Consecutive Duplicates

Related Problems

Takeaways