Score of Parentheses — Editorial

Opening the reading…

Intuitiona closing parenthesis tells you exactly when one score is complete

The score rules describe a tree hidden inside the string. A pair of parentheses creates one group; adjacent groups contribute by addition, while a group wrapped around another contributes twice its inside score. You cannot finish an outer group until every group inside it has been evaluated, so the most recently opened unfinished group must be handled first.

Give every opening parenthesis its own running score, initially zero. A closing parenthesis ends the current group: if its inside score is zero, the group is the primitive pair (), worth 1; otherwise its inside score is doubled. Add that finished value to the surrounding group, because adjacent completed groups are combined by addition.

Approach

Push a zero before processing the string, because this bottom entry collects the score of all top-level groups and gives every completed group a parent to receive its value.

For each opening parenthesis, push a new zero, because all characters until its matching close belong to a deeper group and must not immediately change the enclosing score.

For each closing parenthesis, read and remove the top score, because the top entry represents the group that has just become complete.

Turn that inner score into max(2 * inner, 1), because a nonempty group is nested and must double its inside score, while an empty pair () has score 1 instead of zero.

Add the completed value to the new top entry, because the group is now one component of its enclosing group or of the top-level concatenation.

After every character has been processed, return the bottom entry, because balanced input has closed every group and all scores have flowed back to the sentinel level.

Complexityeach parenthesis changes one stack entry once

MEASURE	BOUND	WHY
Time	O(n)	The loop examines each of the n characters once. Each opening causes one push and each closing causes one pop, constant-time arithmetic, and one addition, so no substring or completed group is scanned again.
Space	O(n)	The output is a single integer and is excluded from extra space. The stack stores one entry for each currently open level plus the sentinel; in the worst shape, such as deeply nested parentheses, that is O(n), while shallower input uses less.

Here n is the length of the parentheses string.

Annotated solutionC++ · stack simulation · one entry per open depth

CPPA stack stores the unfinished score at every open-parenthesis depth.

#include <algorithm>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);

        for (char c : s) {
            if (c == '(') {
                st.push(0);
            } else {
                int inside = st.top();
                st.pop();
                int value = max(2 * inside, 1);
                st.top() += value;
            }
        }

        return st.top();
    }
};

The sentinel zero is what makes concatenation work without a special case. For ()(), the first close adds 1 to the sentinel and the second close adds another 1 to the same entry. For (()), the inner close adds 1 to the inner group, and the outer close doubles that result before adding it to the sentinel.

The depth-counting alternativean O(1)-space optimization when only primitive groups need direct scoring

You can avoid the stack because every primitive pair contributes a power of two determined by its nesting depth. When a close follows an opening parenthesis, that pair is exactly (), and its contribution is 2 raised to the depth after the close. A close at depth 0 contributes 1, a close at depth 1 contributes 2, and so on. Other closing parentheses only finish a nonempty group whose contribution was already accounted for by its innermost primitive pairs.

CPPA depth counter adds the power-of-two contribution of each primitive pair.

#include <string>
using namespace std;

class Solution {
public:
    int scoreOfParentheses(string s) {
        int depth = 0;
        int score = 0;

        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
            if (s[i] == '(') {
                ++depth;
            } else {
                --depth;
                if (s[i - 1] == '(') {
                    score += 1 << depth;
                }
            }
        }

        return score;
    }
};

This is an optimization, not merely a different arrangement: it reduces extra space from O(n) to O(1), while time remains O(n). The tradeoff is less direct bookkeeping. The stack mirrors the three scoring rules and is easier to adapt if the representation or scoring rules change; the depth version depends on the special power-of-two structure of these parentheses rules.