Remove invalid Parentheses

XXX. Remove Invalid Parentheses

Recursion

Backtracking

String

Problem Statement:

Given a string s containing parentheses '(' and ')', remove the minimum number of invalid parentheses to make the string valid. Return all possible results. The answer may be returned in any order.

Algorithm:

1. Iterate through the string to count mismatched parentheses:
   • Increment the count of open parentheses when encountering '('.
   • Increment the count of close parentheses when encountering ')'.
   • If at any point close parentheses outnumber open ones, backtrack by removing a ')'.
2. Use recursion to systematically remove parentheses and avoid duplicates by skipping consecutive parentheses in the same position.
3. Once no invalid parentheses are detected, reverse the string and repeat the process for the opposite parentheses.
4. If the reversed string is valid, add it to the result set.

Complexity:

Time: O(2ⁿ), where n is the length of the string | Space: O(n) for recursion stack and results.

Java Implementation:

class Solution {

    public List removeInvalidParentheses(String s) {
        List output = new ArrayList<>();
        removeHelper(s, output, 0, 0, '(', ')');
        return output;
    }

    // Helper function to recursively remove invalid parentheses
    public void removeHelper(String s, List output, int iStart, int jStart, char openParen, char closedParen) {
        int numOpenParen = 0, numClosedParen = 0;

        // Count mismatched parentheses
        for (int i = iStart; i < s.length(); i++) {
            if (s.charAt(i) == openParen) numOpenParen++;
            if (s.charAt(i) == closedParen) numClosedParen++;

            // If more closed parentheses than open, backtrack
            if (numClosedParen > numOpenParen) {
                for (int j = jStart; j <= i; j++) {
                    // Avoid duplicates by skipping consecutive invalid parentheses
                    if (s.charAt(j) == closedParen && (j == jStart || s.charAt(j - 1) != closedParen)) {
                        // Remove the invalid parenthesis and recurse
                        removeHelper(s.substring(0, j) + s.substring(j + 1), output, i, j, openParen, closedParen);
                    }
                }
                return; // Stop further processing
            }
        }

        // No invalid closed parentheses found, reverse and check the opposite
        String reversed = new StringBuilder(s).reverse().toString();

        if (openParen == '(') 
            removeHelper(reversed, output, 0, 0, ')', '(');
        else 
            output.add(reversed); // Add valid result to output
    }
}