Code Implementation

class Solution:
    def checkValidString(self, s: str) -> bool:
        low = 0  # Minimum open '(' count
        high = 0 # Maximum open '(' count

        for c in s:
            if c == '(':
                low += 1
                high += 1
            elif c == ')':
                low -= 1
                high -= 1
            else: # c == '*'
                low -= 1   # Treat '*' as ')'
                high += 1  # Treat '*' as '('

            if high < 0:
                return False
            if low < 0:
                low = 0

        return low == 0
      

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        for (char c : s) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else { // c == '*'
                low--;
                high++;
            }
            if (high < 0) return false;
            if (low < 0) low = 0;
        }
        return low == 0;
    }
};
      

class Solution {
    public boolean checkValidString(String s) {
        int low = 0, high = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else { // c == '*'
                low--;
                high++;
            }
            if (high < 0) return false;
            if (low < 0) low = 0;
        }
        return low == 0;
    }
}
      

var checkValidString = function(s) {
    let low = 0, high = 0;
    for (let c of s) {
        if (c === '(') {
            low++;
            high++;
        } else if (c === ')') {
            low--;
            high--;
        } else { // c === '*'
            low--;
            high++;
        }
        if (high < 0) return false;
        if (low < 0) low = 0;
    }
    return low === 0;
};
      

Problem Description

The "Valid Parenthesis String" problem asks you to determine whether a given string s, containing only the characters '(', ')', and '*', is valid. A string is considered valid if:

• Every '(' has a corresponding ')' and vice versa, in the correct order.
• The '*' character can represent either '(', ')', or an empty string.
• The string may be empty, which is considered valid.

Your goal is to return true if the string is valid according to these rules, and false otherwise.

Thought Process

At first glance, this problem looks similar to the classic "Valid Parentheses" problem, but the addition of the '*' wildcard makes it more complex. A brute-force approach would be to try all possible replacements for each '*' (as '(', ')', or empty), and check if any combination results in a valid string. However, this quickly becomes infeasible as the number of '*' increases, due to exponential growth in possibilities.

To optimize, we need a way to account for the flexibility of '*' without actually generating every possibility. The key insight is to track the possible "range" of open parentheses counts as we scan the string, considering the best and worst cases for each '*'.

Solution Approach

We use a greedy algorithm that keeps track of two variables as we scan the string from left to right:

• low: The minimum number of open parentheses that could be valid up to the current character (assuming every '*' is a ')').
• high: The maximum number of open parentheses that could be valid (assuming every '*' is a '(').

For each character:

1. If it's '(', increment both low and high (since an open parenthesis must be matched later).
2. If it's ')', decrement both low and high (since we close an open parenthesis).
3. If it's '*', decrement low (treating '*' as ')'), and increment high (treating '*' as '(').

• If at any point high becomes negative, too many closing parentheses have appeared and the string can't be valid.
• If low drops below zero, reset it to zero (since low can't be negative; we can't have fewer than zero unmatched opens).

At the end, if low is zero, then there is at least one way to interpret the '*' characters such that the string is valid.

Example Walkthrough

Let's walk through the string "(*)":

1. Character 1: '('
   • low = 1, high = 1
2. Character 2: '*'
   • low = 0 (if '*' is ')'), high = 2 (if '*' is '(')
3. Character 3: ')'
   • low = -1, high = 1
   • Since low is negative, set low = 0

At the end, low = 0, so the string is valid.

Time and Space Complexity

• Brute-force approach: For each '*' in the string, there are 3 choices, so the time complexity is O(3^k), where k is the number of '*' characters. This is exponential and not feasible for large strings.
• Optimized (greedy) approach: We scan the string once, updating low and high in O(1) time per character. So the overall time complexity is O(n), where n is the length of the string. Space complexity is O(1), since we only use a few variables.

Summary

The Valid Parenthesis String problem can be solved efficiently by tracking the possible range of open parentheses using a greedy scan. By considering the flexibility of '*' at each step, we avoid the need for brute-force enumeration. This approach gives an elegant O(n) time, O(1) space solution, making it suitable for even large input sizes.