https://leetcode.com/problems/score-of-parentheses

When you see parentheses in problem forlumation you should think about stack and indeed, there is stack solution for this problem. This solution will be optimal in time, but in place we can do better! Let us look at the following string: (((()))(()(()))) and try tu understand what will be the score of such string. First of all it can be written as 2 * ((()))(()(())), which can be written as 2*((())) + 2*(()(())) = 2*2*(()) + 2*2*() + 2*2*(()) = 2*2*2 + 2*2 + 2*2*2 = 20 and it helps us to notice that what acutally matters is how many () we meet in our string, and how deep they are located. So, let us traverse through our string, keep bal: balance, or depth of current place, that is how many brackets we need to close to get correct expression, and also if we see (), we update ans += 1<< bal.

Complexity: time complexity is O(n): we need to traverse our string once, space complexity is just O(1).

class Solution:
    def scoreOfParentheses(self, S):
        ans, bal = 0, 0
        for i, s in enumerate(S):
            bal = bal + 1 if s == "(" else bal - 1
            if i > 0 and S[i-1:i+1] == "()":
                ans += 1 << bal
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0856