Remove Invalid Parentheses

HARD

Description

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("
Output: [""]

Constraints:

1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'.
There will be at most 20 parentheses in s.

Approaches

Checkout 3 different approaches to solve Remove Invalid Parentheses. Click on different approaches to view the approach and algorithm in detail.

Brute Force - Generate All Subsequences

This approach generates all possible subsequences of the input string by either including or excluding each character. For each subsequence, we check if it forms a valid parentheses string. Among all valid strings, we keep only those with the maximum length (minimum removals).

Algorithm

Use recursion to generate all possible subsequences
At each position, try both including and excluding the character
Check if each generated subsequence is a valid parentheses string
Among all valid strings, keep only those with maximum length
Return the result as a list

The brute force approach uses recursion to generate all possible subsequences of the input string. At each position, we have two choices: include the current character or exclude it. We recursively explore both possibilities and collect all valid parentheses strings. Finally, we filter the results to keep only those with minimum removals.

public List<String> removeInvalidParentheses(String s) {
    Set<String> result = new HashSet<>();
    generateSubsequences(s, 0, "", result);
    
    // Find maximum length among valid strings
    int maxLen = 0;
    for (String str : result) {
        maxLen = Math.max(maxLen, str.length());
    }
    
    // Keep only strings with maximum length
    List<String> finalResult = new ArrayList<>();
    for (String str : result) {
        if (str.length() == maxLen) {
            finalResult.add(str);
        }
    }
    
    return finalResult;
}

private void generateSubsequences(String s, int index, String current, Set<String> result) {
    if (index == s.length()) {
        if (isValid(current)) {
            result.add(current);
        }
        return;
    }
    
    // Include current character
    generateSubsequences(s, index + 1, current + s.charAt(index), result);
    
    // Exclude current character
    generateSubsequences(s, index + 1, current, result);
}

private boolean isValid(String s) {
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') count++;
        else if (c == ')') {
            count--;
            if (count < 0) return false;
        }
    }
    return count == 0;
}

Complexity Analysis

Time Complexity: O(2^n * n) where n is the length of string. We generate 2^n subsequences and each validation takes O(n) timeSpace Complexity: O(2^n * n) for storing all possible subsequences and the recursion stack

Pros and Cons

Pros:

Simple and straightforward approach
Guaranteed to find all possible solutions
Easy to understand and implement

Cons:

Extremely inefficient for larger inputs
Generates many unnecessary subsequences
High memory usage due to storing all subsequences

Code Solutions

Checking out 3 solutions in different languages for Remove Invalid Parentheses. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Remove Invalid Parentheses

Algorithms:

Breadth-First Search

Patterns:

Backtracking

Data Structures:

String

Companies:

Google |Snowflake |Rubrik |Deliveroo |