'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List

class Solution:
    '''
    Keep track of the balance of the string, as defined in Approach #1. 
    For every ) that immediately follows a (, the answer is 1 << balance, 
    as balance is the number of exterior set of parentheses that contains 
    this core.
    '''
    def scoreOfParentheses2(self, S: str) -> int:
        ans = bal = 0
        for i, x in enumerate(S):
            if x == '(':
                bal += 1
            else:
                bal -= 1
                if S[i-1] == '(':
                    ans += 1 << bal # 2^bal
        return ans
        
        
    # stack
    # O(N) for S and T
    def scoreOfParentheses1(self, S: str) -> int:
        stack = [0] # score of current frame
        
        for p in S:
            if p == "(":
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)
        return stack.pop()
    
    
    # divide and conquer
    # O(N^2) for N as the length of S
    # O(N) for the stack
    def scoreOfParentheses(self, S: str) -> int:
        def helper(i, j):
            # Score of balanced string S[i:j]
            res = balance = 0
            
            # Split string into primitives
            for k in range(i, j):
                balance += 1 if S[k] == "(" else -1
                if balance == 0:
                    if k - i == 1:
                        res += 1
                    else:
                        res += 2 * helper(i + 1, k) # attention: i + 1 !!!
                    i = k + 1
            return res
            
        
        return helper(0, len(S))
        