LC678. Valid Parenthesis String

Approach 1: Using Stacks

class Solution:
    def checkValidString(self, s: str) -> bool:
        # We need to keep track of '(' as usual for a valid
        # parens problem
        open_stack = []
        # We'll need to know where '*' was seen last so
        # we keep a stack for it
        star_stack = []
 
        for i, c in enumerate(s):
            if c == '*':
                # Note that we are storing the index here, since
                # storing '*' is kinda pointless and we need to know
                # closest occurrence of a '*'
                star_stack.append(i)
            elif c == '(':
                # Same here, not much point in keeping '(' so we keep
                # the index
                open_stack.append(i)
            elif c == ')':
                # Case 1: We ran out of '('! Normally, we'd say
                # this is invalid string but in this case, we need
                # to see if have '*' to our rescue
                if not open_stack:
                    # If we don't have any '*', we can't save the string
                    # and thus it's invalid
                    if not star_stack:
                        return False
                    
                    # If we do, then let's assume this is a '(' and pop it off
                    # from starstack since we used that '*'
                    star_stack.pop()
                else:
                    # It's business as usual otherwise if we have actual '(' in
                    # stack
                    open_stack.pop()
        
        # Now that we're out of the main loop, we only need to worry about stray
        # '(' and see if we can convert * → )
        while open_stack and star_stack:
            # Since '(' must always occur before ')', we can't simply use any '*'
            # available in the stack. It should be an '*' that occurs after the 
            # most recent '(' or else it'd be like ')(' which is invalid. We keep
            # doing this as much as we can.
            if star_stack.pop() < open_stack.pop():
                return False
        
        # If even after all that, the stack is still not empty, the string is invalid
        return len(open_stack) == 0

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 2: Greedy (Optimal)

class Solution:
    def checkValidString(self, s: str) -> bool:
        # Greedy approach
        # Min and max possible open parenthesis
        open_min, open_max = 0, 0
 
        for c in s:
            if c == '(':
                open_min, open_max = open_min + 1, open_max + 1
            elif c == ')':
                open_min, open_max = open_min - 1, open_max - 1
            elif c == '*':
                # If we assume '*' as ')', that'd get us to fewer open parens
                # so we decrement `open_min` by 1
                # Similarly, we assume '*' as '(', we can keep adding more to
                # num of open parens
                # The other case is '*' being empty string which doesn't affect
                # these counts anyway
                open_min, open_max = open_min - 1, open_max + 1
            
            # If after assuming '*' being '(' we still find open_max to be -ve,
            # there's no way to save the string and hence it's invalid
            if open_max < 0:
                return False
            
            # open_min is allowed to go below 0 and when we do, we just reset it
            # back to zero and assume the recent '*' was an empty string. We already
            # would've bailed in the previous condition if open_max turned out be -ve
            # as that'd have meant we can't compensate for the extra ')' with *
            if open_min < 0:
                open_min = 0
 
        return open_min == 0

Complexity

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