Remove invalid Parentheses

XXX. Remove Invalid Parentheses

Backtracking

Recursion

Problem Statement:

Given a string s containing parentheses and lowercase letters, remove the minimum number of invalid parentheses to make the input string valid. Return all possible results in any order.

Algorithm:

The solution uses a backtracking approach with recursion:

1. Traverse the string and keep count of open and closed parentheses.
   • If at any point the count of closed parentheses exceeds the count of open ones, identify the invalid parentheses to remove.
2. Use recursion to generate all valid possibilities by removing invalid parentheses.
   • To avoid duplicates, ensure you do not remove two consecutive parentheses at the same index.
3. After processing in one direction (left to right), reverse the string and repeat the process to ensure both open and closed parentheses are handled.
4. Add valid results to the output list.

Complexity:

Time Complexity: O(2ⁿ), where n is the length of the string. In the worst case, all subsets of parentheses are checked.
Space Complexity: O(n), for the recursion stack and intermediate strings.

Java Implementation:

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

    private void removeHelper(String s, List output, int iStart, int jStart, char openParen, char closedParen) {
        int numOpenParen = 0, numClosedParen = 0;
        for (int i = iStart; i < s.length(); i++) {
            if (s.charAt(i) == openParen) numOpenParen++;
            if (s.charAt(i) == closedParen) numClosedParen++;
            if (numClosedParen > numOpenParen) { // Extra closed parenthesis detected
                for (int j = jStart; j <= i; j++) {
                    // Remove duplicate parentheses and recurse
                    if (s.charAt(j) == closedParen && (j == jStart || s.charAt(j - 1) != closedParen)) {
                        removeHelper(s.substring(0, j) + s.substring(j + 1), output, i, j, openParen, closedParen);
                    }
                }
                return; // Stop further processing; recursion handles the rest
            }
        }
        
        // Reverse string and process the opposite direction
        String reversed = new StringBuilder(s).reverse().toString();
        if (openParen == '(')
            removeHelper(reversed, output, 0, 0, ')', '(');
        else
            output.add(reversed); // Valid result found
    }
}