Approach: Stack of running scores

def scoreOfParentheses(s):
    st = [0]
    for c in s:
        if c == "(": st.append(0)
        else:
            v = st.pop()
            st[-1] += max(2*v, 1)
    return st[0]

Complexity: O(n) time, O(n) space.

Full Solution — all languages

class Solution:
    def scoreOfParentheses(self, s):
        st = [0]
        for c in s:
            if c == "(":
                st.append(0)
            else:
                v = st.pop()
                st[-1] += max(2 * v, 1)
        return st[0]

import java.util.*;
class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(0);
        for (char c : s.toCharArray()) {
            if (c == '(') st.push(0);
            else {
                int v = st.pop();
                st.push(st.pop() + Math.max(2 * v, 1));
            }
        }
        return st.peek();
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int scoreOfParentheses(string s) {
        vector<int> st = {0};
        for (char c : s) {
            if (c == '(') st.push_back(0);
            else {
                int v = st.back();
                st.pop_back();
                st.back() += max(2 * v, 1);
            }
        }
        return st[0];
    }
};

/**
 * @param {string} s
 * @return {number}
 */ var scoreOfParentheses = function(s) {
    const st = [0];
    for (const c of s) {
        if (c === '(') st.push(0);
        else {
            const v = st.pop();
            st[st.length - 1] += Math.max(2 * v, 1);
        }
    }
    return st[0];
};

Score of Parentheses

Example 1

Example 2

Example 3

Example 4

Constraints