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

Valid Parenthesis String

Check if parenthesis string with wildcards is valid.

LeetCode ↗

Approach: Greedy (Track Min/Max Open)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Check if parenthesis string with wildcards is valid.

Constraints

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

Solution — Greedy (Track Min/Max Open)

O(n) O(1)

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)