valid_parentheses_string.py

"""
https://leetcode.com/problems/valid-parenthesis-string/description/

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:
Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:
Input: s = "()"
Output: true

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

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

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


def checkValidString(s: str) -> bool:
    leftMin = 0
    leftMax = 0

    for val in s:
        if val == "(":
            leftMin += 1
            leftMax += 1
        if val == ")":
            leftMin -= 1
            leftMax -= 1
        if val == "*":
            leftMin -= 1
            leftMax += 1

        if leftMax < 0:
            return False
        if leftMin < 0:
            leftMin = 0

    return leftMin == 0 or leftMax == 0