Valid Parenthesis String

Medium Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid. '*' can be treated as either (, ), or an empty string.

Example 1:

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

Optimal Solution

Python

Approach: Greedy Min/Max Open Count

Maintain min_open and max_open counts of unclosed (. For (, increment both. For ), decrement both. For *, decrement min (treat as )) and increment max (treat as (). If max_open drops below 0, string is invalid. Reset min_open to 0 if it goes negative. Valid if min_open == 0 at the end.

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open = max_open = 0

        for c in s:
            if c == '(':
                min_open += 1
                max_open += 1
            elif c == ')':
                min_open = max(0, min_open - 1)
                max_open -= 1
            else:
                min_open = max(0, min_open - 1)
                max_open += 1

            if max_open < 0:
                return False

        return min_open == 0