10. Regular Expression Matching

"""
main idea: evenly distribute parentheses into A, B two groups. 
there are different ways to seperate them,  one common approach is to use accumutive open parentheses' odd/even  property to mark one group   
e.g. 

cnt 1 0 1 2 1 0 1 0 
idx 0 1 2 3 4 5 6 7      when [c == '('  and cnt %2 == 1 ] OR [  c == ')' and cnt%2==0 ], set res[i] = 1  
    ( ) ( ( ) ) ( )
    ^ ^ ^     ^ ^ ^
tc O(N) sc O(N)
"""
class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        
        n = len(seq)
        res = [0] *n
        cnt = 0
        for i,c in enumerate(seq):
            if c == '(':
                cnt += 1
                res[i] = cnt%2
            else:
                cnt -= 1
                res[i] = (cnt+1)%2     
        return res 

"""
tc O(N) sc O(N)
"""
class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        res = [] 
        l = r  = 0 
        for i,c in enumerate(seq):
            res.append(i&1 ^(c == '('))
        return res