Valid Parenthesis String

Problem Description

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Examples

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'

Solution Approach

This problem can be solved using a greedy approach with two-pass validation:

Key Insight

The asterisk * can represent three possibilities: left parenthesis, right parenthesis, or empty string. We need to track the possible range of open parentheses count.

Algorithm

We track two values:

• minOpen: minimum possible number of open parentheses
• maxOpen: maximum possible number of open parentheses

For each character:

1. If '(': both min and max increase by 1
2. If ')': both min and max decrease by 1
3. If '*':
   • min decreases by 1 (treating * as ')' or empty)
   • max increases by 1 (treating * as '(')

Validation:

• If maxOpen < 0 at any point, we have too many ')' → return false
• If minOpen < 0, reset it to 0 (we can treat some * as empty)
• At the end, minOpen should be 0 (all parentheses balanced)

Greedy Strategy

The greedy choice is to maintain the range of possible open parentheses counts, always considering the most optimistic (maxOpen) and pessimistic (minOpen) scenarios.

Example Walkthrough

For `s = "(*))"``:

1. '(': minOpen=1, maxOpen=1
2. '*': minOpen=0, maxOpen=2
3. ')': minOpen=-1→0, maxOpen=1
4. ')': minOpen=-1→0, maxOpen=0
5. Result: minOpen=0 → return true

Time & Space Complexity

• Time Complexity: O(n) where n is the length of the string
• Space Complexity: O(1) - only using two variables

Java Solution

class Solution {
    public boolean checkValidString(String s) {
        int minOpen = 0;  // Minimum possible open parentheses
        int maxOpen = 0;  // Maximum possible open parentheses

        for (char c : s.toCharArray()) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen--;
                maxOpen--;
            } else { // c == '*'
                minOpen--; // Treat as ')' or empty
                maxOpen++; // Treat as '('
            }

            // Too many closing parentheses
            if (maxOpen < 0) {
                return false;
            }

            // Reset minOpen if it goes negative
            if (minOpen < 0) {
                minOpen = 0;
            }
        }

        // Check if we can balance all parentheses
        return minOpen == 0;
    }
}

Python Solution

def checkValidString(s: str) -> bool:
    min_open = 0  # Minimum possible open parentheses
    max_open = 0  # Maximum possible open parentheses

    for c in s:
        if c == '(':
            min_open += 1
            max_open += 1
        elif c == ')':
            min_open -= 1
            max_open -= 1
        else:  # c == '*'
            min_open -= 1  # Treat as ')' or empty
            max_open += 1  # Treat as '('

        # Too many closing parentheses
        if max_open < 0:
            return False

        # Reset min_open if it goes negative
        if min_open < 0:
            min_open = 0

    # Check if we can balance all parentheses
    return min_open == 0

Alternative Approach: Two-Pass Scan

Another approach is to scan the string twice:

public boolean checkValidString(String s) {
    // Left to right: check if there are too many ')'
    int balance = 0;
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '*') balance++;
        else balance--;
        if (balance < 0) return false;
    }

    // Right to left: check if there are too many '('
    balance = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        char c = s.charAt(i);
        if (c == ')' || c == '*') balance++;
        else balance--;
        if (balance < 0) return false;
    }

    return true;
}

This approach scans twice: first treating * as (, then treating * as ).