LC 0678 [M] Valid Parenthesis String - ALawliet/algorithms GitHub Wiki

start with checking the right first and allow a left or wildcard to pair it

https://www.youtube.com/watch?v=2ef4_2R4rg8

class Solution:
    def checkValidString(self, s: str) -> bool:
        # what makes a string invalid?
        # 1. we have too many right tokens. not enough left/wild to pair
        
        leftWild = 0
        left = 0
        
        for c in s:
            # making sure all our right tokens have a pair
            if c == ')':
                if leftWild == 0: return False
                leftWild -= 1
            else:
                leftWild += 1
                
            # making sure all our left tokens have a pair
            if c == '(':
                left += 1
            else:
                left = max(0, left - 1)
                
        return left == 0