Leetcode 856. Score of Parentheses

Given a balanced parentheses string S, compute the score of the string based on the following rule:

• () has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Note:

1. S is a balanced parentheses string, containing only ( and ).
2. 2 <= S.length <= 50

Code (Java):

class Solution {
    public int scoreOfParentheses(String S) {
        if (S == null || S.length() == 0) {
            return 0;
        }

        int ans = 0;        
        Stack<Integer> stack = new Stack<>();
        
        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(-1);
            } else {
                int curr = 0;
                while (stack.peek() != -1) {
                    curr += stack.pop();
                }
                
                stack.pop(); // '('
                
                if (curr == 0) {
                    curr = 1;
                } else {
                    curr *= 2;
                }
                stack.push(curr);
            }
        }
        
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        
        return ans;
    }
}

Solution 2: O(1) space
We use a counter to maintain the number of open left parenthesis.
If the current char is '(', counter++
If the current is ')', counter--
If the current is "()" we know the current number of open left parentheiss outside,
then score += 1 << counter
The key observation for the solution is score of (()()()) = (()) + (()) + (()), so we can calculate
the score and sum it up.
Code (Java):

class Solution {
    public int scoreOfParentheses(String S) {
        int left = 0;
        int score = 0;
        
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if (c == '(') {
                left++;
            } else {
                left--;
                if (S.charAt(i - 1) == '(') {
                    score += 1 << left;
                }
            }
        }
        
        return score;
    }
}