Valid Parenthesis String

How it works

We want to check whether a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

Instead of trying all possibilities or using stacks, we can solve this greedily by tracking a range of possible unmatched '(' counts.

Think of it this way:

• At any point, we don’t need the exact number of open parentheses
• We only need to know the minimum and maximum number of '(' that could be open

Why this works:

• '(' always increases the number of open parentheses
• ')' always decreases it
• '*' is flexible and can:
  • decrease open count (act as ')')
  • increase open count (act as '(')
  • keep it unchanged (act as empty)

So we maintain:

• leftMin → the minimum possible number of unmatched '('
• leftMax → the maximum possible number of unmatched '('

If at any point the maximum possible opens becomes negative, the string is invalid. At the end, if the minimum possible opens is zero, the string can be valid.

Steps

1. Initialize two counters:
   • leftMin = 0
   • leftMax = 0
2. Traverse the string character by character:
3. For each character c:
   • If c == '(':
     • increment both leftMin and leftMax
   • If c == ')':
     • decrement both leftMin and leftMax
   • If c == '*':
     • treat it flexibly:
       • leftMin -= 1 (as ')')
       • leftMax += 1 (as '(')
4. If leftMax < 0 at any point:
   • return false (too many closing parentheses)
5. If leftMin < 0:
   • reset leftMin = 0 (we can treat extra closings as empty)
6. After processing the entire string:
   • return true if leftMin == 0, else false

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting That Wildcards Have Three Options

A common mistake is treating '*' as only representing '(' or ')'. Remember that '*' can also represent an empty string. This third option is crucial for cases like "(*)" where the '*' should be treated as empty to form a valid string.

Not Checking for Negative Open Count

When processing ')' or treating '*' as ')', you must ensure the open parenthesis count never goes negative. A negative count means there are more closing parentheses than opening ones at that point, which is invalid regardless of what comes later. Always check open >= 0 before proceeding.

Ignoring the Position of Wildcards in Stack Approach

In the stack-based solution, simply counting unmatched '(' and '*' is not enough. You must also verify that each remaining '(' has a '*' that appears after it (at a higher index). A '*' appearing before a '(' cannot act as a matching ')' for it.

class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin, leftMax = 0, 0

        for c in s:
            if c == "(":
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ")":
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1
            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin = 0
        return leftMin == 0

class Solution {
public:
    bool checkValidString(string s) {
        int leftMin = 0, leftMax = 0;

        for (char c : s) {
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) {
                return false;
            }
            if (leftMin < 0) {
                leftMin = 0;
            }
        }
        return leftMin == 0;
    }
};