Remove Invalid Parentheses

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.

Approach: BFS over Removals

Algorithm

1. Compute how many '(' and ')' must be removed to balance the string
2. Run DFS that removes characters one at a time while tracking the balance:

• A '(' increments balance, a ')' decrements it; skip removals when balance would go negative
• Remove only as many of each type as needed

3. When the string is fully processed with balance 0 and the required removals are used, add it to the result

Time & Space Complexity

• Time Complexity: O(2^P) worst case - P is the number of parentheses; bounded by the small constraint
• Space Complexity: O(P) for the recursion depth, plus O(R) for the unique results

Java Implementation

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RemoveInvalidParentheses {

    /**
     * Return unique strings valid after the minimum number of removals.
     * @param s Input string
     * @return List of valid strings
     */
    public List<String> removeInvalidParentheses(String s) {
        int removeOpen = 0;
        int removeClose = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                removeOpen++;
            } else if (c == ')') {
                if (removeOpen > 0) {
                    removeOpen--;
                } else {
                    removeClose++;
                }
            }
        }

        Set<String> result = new HashSet<>();
        dfs(s, 0, removeOpen, removeClose, 0, new StringBuilder(), result);
        return new ArrayList<>(result);
    }

    private void dfs(String s, int index, int removeOpen, int removeClose,
                     int balance, StringBuilder current, Set<String> result) {
        if (index == s.length()) {
            if (balance == 0 && removeOpen == 0 && removeClose == 0) {
                result.add(current.toString());
            }
            return;
        }

        char c = s.charAt(index);

        if (c == '(' && removeOpen > 0) {
            dfs(s, index + 1, removeOpen - 1, removeClose, balance, current, result);
        }
        if (c == ')' && removeClose > 0) {
            dfs(s, index + 1, removeOpen, removeClose - 1, balance, current, result);
        }

        current.append(c);
        if (c == '(') {
            dfs(s, index + 1, removeOpen, removeClose, balance + 1, current, result);
        } else if (c == ')') {
            if (balance > 0) {
                dfs(s, index + 1, removeOpen, removeClose, balance - 1, current, result);
            }
        } else {
            dfs(s, index + 1, removeOpen, removeClose, balance, current, result);
        }
        current.deleteCharAt(current.length() - 1);
    }

    // Test method
    public static void main(String[] args) {
        RemoveInvalidParentheses rip = new RemoveInvalidParentheses();
        System.out.println("Input: s = \"()())()\"");
        System.out.println("Output: " + rip.removeInvalidParentheses("()())()"));
        // Expected: ["(())()","()()()"]

        System.out.println("Input: s = \")(\"");
        System.out.println("Output: " + rip.removeInvalidParentheses(")("));
        // Expected: [""]
    }
}

Example Walkthrough

For s = "()())()":

1. Count removals: one extra ')' -> removeOpen=0, removeClose=1
2. DFS explores removing each ')' candidate, keeping balance non-negative
3. Removing the third character gives ”(())()”; removing the fourth gives ”()()()”
4. Both are balanced and use exactly one removal -> they form the answer

Key Points

1. Precompute Removals: One pass finds how many '(' and ')' must be dropped
2. Balance Constraint: Skipping ')' when balance is 0 prevents invalid intermediate strings
3. Exact Removal Budget: Both counters must reach 0 at the end of the string
4. Set for Uniqueness: Different removal orders can yield the same string, so a set deduplicates
5. Small Input: The limit of 20 parentheses keeps the exponential search tractable