Valid Parenthesis String

MediumGreedyNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given a string s made of '(', ')', and '*'. Each '*' can act as '(', as ')', or as nothing. Return true if some choice for the stars makes s a well-formed parenthesis string, where every ')' closes an earlier open '(' and every '(' is closed by the end.

Examples

s = "(*))" returns true

Reading the star as "(" gives "(())".

s = "((*" returns false

Two opens need two closes, and a single star can supply only one.

s = "*(" returns false

The final '(' has nothing after it to close it, whatever the star becomes.

Constraints

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

Hints

Hint 1

With no stars, one counter of open parentheses is enough. What changes when a character could move that counter up, down, or not at all?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Track the range of possible open counts instead of one count. lo is the fewest opens possible so far and hi is the most. '(' raises both, ')' lowers both, and '*' lowers lo and raises hi. If hi drops below 0, there are too many closes and no choice can recover, so return false. lo is clamped at 0, since a star that would close a nonexistent open can be read as empty instead. At the end, the string is valid when lo is 0. O(n) time, O(1) space.

Time

O(n)

Space

O(1)

Pitfall

Treating stars as a pool of spare characters without regard to position. A star after a '(' can close it, but a star before the '(' can't, as "*(" shows.

Solutions

class Solution {
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                lo--;
                hi--;
            } else {
                lo--;
                hi++;
            }
            if (hi < 0) return false;
            lo = Math.max(lo, 0);
        }
        return lo == 0;
    }
}

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0
        for c in s:
            if c == "(":
                lo += 1
                hi += 1
            elif c == ")":
                lo -= 1
                hi -= 1
            else:
                lo -= 1
                hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0