Remove Invalid Parentheses

Problem Statement

Given a string s comprised of lowercase English letters and parentheses, the task is to manipulate the string by removing the least number of characters possible so that the resulting string is valid. A valid string in this context is defined as one where every opening parenthesis '(' has a corresponding closing parenthesis ')'. The goal is to generate a list of unique valid strings by performing minimal removals of invalid parentheses from the given string. The resulting list can be returned in any order.

Examples

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 and Intuition

1. Understanding Valid Parentheses:

   • A string is considered valid if every opening bracket '(' is matched and closed by a corresponding closing bracket ')'.
   • To validate the string, when traversing from left to right, the closing bracket count can never exceed the opening bracket count at any point.

2. Identifying Invalid Parentheses:

   • A closing parenthesis ')' without a preceding matching opening parenthesis '(' is immediately deemed invalid.
   • An excess of opening brackets '(' by the end of the string also deems those brackets as invalid.

3. Strategies to Form Valid Strings:

   • Backtracking: One effective approach to explore all possible strings with the minimum number of removals is to use backtracking. This involves recursively removing each parenthesis that potentially could be invalid and checking if the newly formed string is valid.
   • Tracking Left and Right Parity: As you attempt to form valid strings by removing parentheses, keeping track of the count of left '(' and right ')' parentheses allows you to understand when you've potentially formed a valid string.
   • Minimal Removal: Ensure that the mechanism to remove parentheses always aims for the minimal number of removals. This can be done by stopping further exploration when you have already reached the minimum number required for a valid string.

4. Ensuring Uniqueness:

   • Using a set data structure might be helpful to store resultant strings to avoid duplicates.

5. Optimization Considerations:

   • Since each character could potentially be removed, in the worst case, you are looking at many possibilities, but using the counts of misplaced '(' and ')' can drastically reduce unnecessary computations.
   • Early termination of recursion when a valid string is found with the current minimum removal count helps reduce the solution space.

These strategies, combined with the constraints provided (like the maximum length constraint of 25 characters and at most 20 parentheses), help manage the complexity of the solution, aiming to find results efficiently. The examples given illustrate these principles by showing the minimum removals needed to make the input strings valid and the diverse results that can occur based on the arrangement of parentheses and letters in s.

Solutions

class Solution {
    
  private Set<String> refinedValidExpressions = new HashSet<String>();
    
  private void deepDive(
      String expr,
      int position,
      int openCount,
      int closeCount,
      int openToRemove,
      int closeToRemove,
      StringBuilder partialExpr) {
    
    if (position == expr.length()) {
      if (openToRemove == 0 && closeToRemove == 0) {
        this.refinedValidExpressions.add(partialExpr.toString());
      }
    
    } else {
      char charAtPosition = expr.charAt(position);
      int currentLength = partialExpr.length();
    
      if ((charAtPosition == '(' && openToRemove > 0) || (charAtPosition == ')' && closeToRemove > 0)) {
        this.deepDive(
            expr,
            position + 1,
            openCount,
            closeCount,
            openToRemove - (charAtPosition == '(' ? 1 : 0),
            closeToRemove - (charAtPosition == ')' ? 1 : 0),
            partialExpr);
      }
    
      partialExpr.append(charAtPosition);
    
      if (charAtPosition != '(' && charAtPosition != ')') {
    
        this.deepDive(expr, position + 1, openCount, closeCount, openToRemove, closeToRemove, partialExpr);
    
      } else if (charAtPosition == '(') {
    
        this.deepDive(expr, position + 1, openCount + 1, closeCount, openToRemove, closeToRemove, partialExpr);
    
      } else if (closeCount < openCount) {
    
        this.deepDive(expr, position + 1, openCount, closeCount + 1, openToRemove, closeToRemove, partialExpr);
      }
    
      partialExpr.deleteCharAt(currentLength);
    }
  }
    
  public List<String> removeInvalidParentheses(String expr) {
    
    int leftCount = 0, rightCount = 0;
    
    for (int i = 0; i < expr.length(); i++) {
    
      if (expr.charAt(i) == '(') {
        leftCount++;
      } else if (expr.charAt(i) == ')') {
        rightCount = leftCount == 0 ? rightCount + 1 : rightCount;
        leftCount = leftCount > 0 ? leftCount - 1 : leftCount;
      }
    }
    
    this.deepDive(expr, 0, 0, 0, leftCount, rightCount, new StringBuilder());
    return new ArrayList<String>(this.refinedValidExpressions);
  }
}