Valid Parenthesis String

• Define a recursive function check(s, index, openCount).
• index is the current position in the string, and openCount is the balance of open parentheses.
• Base Case 1: If openCount becomes negative, it's an invalid state, return false.
• Base Case 2: If index reaches the end of the string, the string is valid if and only if openCount is 0.
• Recursive Step:
  • If s[index] is '(', recurse with check(s, index + 1, openCount + 1).
  • If s[index] is ')', recurse with check(s, index + 1, openCount - 1).
  • If s[index] is '*', explore all three possibilities by making three separate recursive calls:
    1. Treat * as '(': check(s, index + 1, openCount + 1).
    2. Treat * as ')': check(s, index + 1, openCount - 1).
    3. Treat * as empty: check(s, index + 1, openCount).
  • Return true if any of the three branches for * return true.

We define a recursive function check(index, open_count) which determines if the substring starting from index is valid, given a current balance of open_count open parentheses.

• The base case for the recursion is when we reach the end of the string (index == s.length()). The string is valid if and only if the open_count is zero.
• Another base case is if open_count ever becomes negative, which means we have an invalid sequence (e.g., a ')' without a preceding '('). In this case, we prune the search path by returning false.
• In the recursive step, for the character at the current index:
  • If it's '(', we increment open_count and recurse on the next index.
  • If it's ')', we decrement open_count and recurse.
  • If it's '*', we branch out and make three recursive calls: one for treating it as '(', one for ')', and one for an empty string. If any of these branches return true, the string is valid.

1class Solution {2    public boolean checkValidString(String s) {3        return check(s, 0, 0);4    }5 6    private boolean check(String s, int index, int openCount) {7        if (openCount < 0) {8            return false;9        }10        if (index == s.length()) {11            return openCount == 0;12        }13 14        char c = s.charAt(index);15        if (c == '(') {16            return check(s, index + 1, openCount + 1);17        } else if (c == ')') {18            return check(s, index + 1, openCount - 1);19        } else { // c == '*'20            // Try all 3 possibilities for '*'21            return check(s, index + 1, openCount + 1) || // as '('22                   check(s, index + 1, openCount - 1) || // as ')'23                   check(s, index + 1, openCount);      // as empty24        }25    }26}

• Use a 2D array, memo[index][openCount], to store the results of subproblems. Initialize it to an 'uncomputed' state.
• The recursive function check(s, index, openCount, memo) is the same as the brute-force one, with two additions:
  1. Memoization Check: At the beginning of the function, check if memo[index][openCount] has already been computed. If so, return the stored result.
  2. Store Result: Before returning a computed result, store it in memo[index][openCount].
• The state is defined by (index, openCount), where index is the position in the string (0 to n) and openCount is the balance of open parentheses (0 to n).

We use a 2D array, memo[index][open_count], to store the result of the function call check(index, open_count). The state is defined by the current position in the string (index) and the current balance of open parentheses (open_count).

• Before computing the result for a state (index, open_count), we first check if it's already in our memo table. If it is, we return the stored value immediately.
• If not, we compute the result as in the brute-force approach.
• After computing the result, we store it in memo[index][open_count] before returning it. This ensures that each of the O(n^2) unique subproblems is solved only once.

1class Solution {2    public boolean checkValidString(String s) {3        // memo[i][j] stores the result for check(s, i, j)4        // 0: not computed, 1: true, 2: false5        int[][] memo = new int[s.length()][s.length() + 1];6        return check(s, 0, 0, memo);7    }8 9    private boolean check(String s, int index, int openCount, int[][] memo) {10        if (openCount < 0) {11            return false;12        }13        if (index == s.length()) {14            return openCount == 0;15        }16        if (memo[index][openCount] != 0) {17            return memo[index][openCount] == 1;18        }19 20        boolean isValid;21        char c = s.charAt(index);22        if (c == '(') {23            isValid = check(s, index + 1, openCount + 1, memo);24        } else if (c == ')') {25            isValid = check(s, index + 1, openCount - 1, memo);26        } else { // c == '*'27            isValid = check(s, index + 1, openCount + 1, memo) || // treat as '('28                      check(s, index + 1, openCount - 1, memo) || // treat as ')'29                      check(s, index + 1, openCount, memo);      // treat as empty30        }31        32        memo[index][openCount] = isValid ? 1 : 2;33        return isValid;34    }35}

• Initialize two stacks: openStack for indices of '(' and starStack for indices of '*'.
• Iterate through the string with index i:
  • If s[i] is '(', push i onto openStack.
  • If s[i] is '*', push i onto starStack.
  • If s[i] is ')':
    • Try to pop from openStack first (prefer matching with a real '(').
    • If openStack is empty, pop from starStack (use a '*' as '(').
    • If both are empty, there's an unmatchable ')', so return false.
• After the loop, openStack may still contain indices of unmatched '('.
• While openStack is not empty:
  • If starStack is empty, there are no '*' left to match the '(', so return false.
  • Pop an index openIdx from openStack and starIdx from starStack.
  • A '*' can only act as a ')' if it appears after the '('. So, if openIdx > starIdx, return false.
• If all '(' in openStack are matched, return true.

We iterate through the string once, using two stacks to keep track of the positions of characters.

• We use one stack, openStack, to store the indices of '(' characters.
• We use another stack, starStack, to store the indices of '*' characters.
• When we encounter a ')' character, we try to match it. We prioritize matching with an open parenthesis, so we first try to pop from openStack. If it's empty, we try to pop from starStack (using the '*' as an opening parenthesis). If both stacks are empty, it's an unmatched ')' and the string is invalid.
• After iterating through the entire string, we may have leftover '(' in openStack. These must be matched by '*'s from starStack. We pop from both stacks. For a valid match, the index of the '*' must be greater than the index of the '('. This is because a '*' must appear after a '(' to be able to act as its corresponding ')'. If we find a '(' at an index greater than a '*', it's an invalid pairing.
• If openStack becomes empty, it means all open parentheses were successfully matched. If openStack is not empty but starStack is, we have unmatched open parentheses, and the string is invalid.

1import java.util.Stack;2 3class Solution {4    public boolean checkValidString(String s) {5        Stack<Integer> openStack = new Stack<>();6        Stack<Integer> starStack = new Stack<>();7 8        for (int i = 0; i < s.length(); i++) {9            char c = s.charAt(i);10            if (c == '(') {11                openStack.push(i);12            } else if (c == '*') {13                starStack.push(i);14            } else { // c == ')'15                if (!openStack.isEmpty()) {16                    openStack.pop();17                } else if (!starStack.isEmpty()) {18                    starStack.pop();19                } else {20                    return false;21                }22            }23        }24 25        // Match remaining open parentheses with asterisks26        while (!openStack.isEmpty() && !starStack.isEmpty()) {27            // An asterisk must appear after the open parenthesis to close it28            if (openStack.peek() > starStack.peek()) {29                return false;30            }31            openStack.pop();32            starStack.pop();33        }34 35        return openStack.isEmpty();36    }37}

• Initialize two integer variables, low = 0 and high = 0.
• low will track the minimum possible number of open brackets, and high will track the maximum.
• Iterate through each character c of the string:
  • If c is '(': increment both low and high.
  • If c is ')': decrement both low and high.
  • If c is '*': decrement low (treating * as )) and increment high (treating * as ().
• After updating the counts for each character, perform two checks:
  1. If high becomes negative, it means there are too many closing parentheses that cannot be balanced. Return false.
  2. Reset low to max(low, 0). This is because low represents the number of required open brackets, which cannot be negative. A negative value implies an excess of closing options, which we can discard by treating some * as empty strings.
• After the loop finishes, the string is valid if and only if low is 0. A non-zero low means there are unmatched open parentheses.

We iterate through the string and maintain two counters: low and high.

• low: Represents the minimum possible number of open parentheses. This is calculated by treating every '*' as a closing parenthesis ')'.
• high: Represents the maximum possible number of open parentheses. This is calculated by treating every '*' as an opening parenthesis '('.

When we see '(': we increment both low and high. When we see ')': we decrement both low and high. When we see '*': we decrement low (best case for closing) and increment high (best case for opening).

At each step, we must ensure two conditions:

1. high must never be negative. If high < 0, it means we have an excess of ')' that cannot be balanced even if all preceding '*'s were '('. The string is invalid.
2. low should be treated as max(low, 0). A negative low means we have more ')' or '*'s (treated as ')') than '('. This is fine, as those extra closing options can be effectively absorbed by treating the '*'s as empty strings. We can't have a "debt" of open parentheses, so we reset the minimum required to 0.

After iterating through the entire string, the string is valid if and only if low is 0. A low > 0 would mean there are unmatched open parentheses that could not be closed even when all available '*'s were used as ')'.

1class Solution {2    public boolean checkValidString(String s) {3        int low = 0;  // Minimum number of open parentheses4        int high = 0; // Maximum number of open parentheses5 6        for (char c : s.toCharArray()) {7            if (c == '(') {8                low++;9                high++;10            } else if (c == ')') {11                low--;12                high--;13            } else { // c == '*'14                low--;  // '*' can be ')'15                high++; // '*' can be '('16            }17 18            // If at any point, the max number of open parens is negative, it's invalid.19            if (high < 0) {20                return false;21            }22            23            // The minimum number of open parens cannot be negative.24            low = Math.max(low, 0);25        }26 27        // At the end, the minimum number of open parens must be 0.28        return low == 0;29    }30}