Problem Statement:

Given a string s containing only '(', ')', and '*', return true if the string is valid.

A string is valid if:

• Every '(' has a corresponding ')'
• Every ')' has a corresponding '('
• '*' can be treated as '(', ')', or an empty string
• The parentheses must be balanced and in correct order

Examples:

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

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

Example 4:

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

The challenge is that '*' can be anything:

• '('
• ')'
• '' (empty string)

This means we need to consider multiple possible interpretations.

Greedy Two-Pointer Method (Optimized O(n) time)

This is the optimal and accepted approach, which uses greedy logic and two counters:

• low: Minimum number of open brackets '(' possible at a point
• high: Maximum number of open brackets '(' possible at a point

We scan the string left to right:

Character	Effect on low	Effect on high
'('	low++	high++
')'	low-- (if > 0)	high--
'*'	low-- or low stays	high++

At any point:

• If high < 0 → too many ')', return false
• If low < 0 → reset to 0 (because * can be empty or '(')

Java Code:

public class ValidParenthesisString {
    public boolean checkValidString(String s) {
        int low = 0;   // min open brackets
        int high = 0;  // max open brackets

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                low++;
                high++;
            } else if (ch == ')') {
                if (low > 0) low--;
                high--;
            } else if (ch == '*') {
                if (low > 0) low--; // treat '*' as ')'
                high++;             // treat '*' as '('
            }

            // If too many ')'
            if (high < 0) return false;
        }

        // If all open brackets are matched
        return low == 0;
    }

    // Testing
    public static void main(String[] args) {
        ValidParenthesisString vps = new ValidParenthesisString();
        System.out.println(vps.checkValidString("(*)"));     // true
        System.out.println(vps.checkValidString("(*))"));    // true
        System.out.println(vps.checkValidString("((*)"));    // true
        System.out.println(vps.checkValidString("(*(()"));   // false
    }
}

Dry Run

Let’s take s = "(*))"

Initialize: low = 0, high = 0

Char	Action	low	high
(	+1 open	1	1
*	-1 or +1 or 0	0	2
)	-1 close	0	1
)	-1 close	0	0

All open brackets are closed → Valid → return true