#129 Medium Time O(n) Space O(1) Animated

Valid Parenthesis String

Check if parenthesis string with wildcards is valid.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Greedy choice with a local proof

Commit to the locally best safe choice only after identifying why it cannot block an optimal answer.

Approach: Greedy (Track Min/Max Open)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Commit to the locally best safe choice only after identifying why it cannot block an optimal answer.

Common Pitfall

Sort or define the selection order before applying the greedy rule.

Description

Check if parenthesis string with wildcards is valid.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Greedy (Track Min/Max Open)

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Order candidates by the greedy criterion.
Inspect the next candidate.
Accept it only when it preserves feasibility.
Return the accumulated result.

def checkValidString(s):
    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: # s = ( * ) (
            leftMin = 0
            
    return leftMin == 0

Partition Labels

Valid Parenthesis String

Steps

Description

Constraints

Tags

Solution — Greedy (Track Min/Max Open)