Valid Parenthesis String: the idea to remember.

The core insight

Maintain the minimum and maximum possible unmatched opens after each prefix.

Why it works

The interval represents every feasible balance: star widens it, closing shifts it down, and negative maximum means no valid interpretation remains.

The mistake to avoid

Clamp the minimum to zero, but reject a negative maximum immediately. A final minimum of zero is required.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Maintain the minimum and maximum possible unmatched opens after each prefix.
public boolean checkValidString(String s) {
    int low = 0, high = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            low++;
            high++;
        } else if (s.charAt(i) == ')') {
            if (low > 0) {
                low--;
            }
            high--;
        } else {
            if (low > 0) {
                low--;
            }
            high++;
        }
        if (high < 0) {
            return false;
        }
    }
    return low == 0;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection