Score of parentheses

XXX. Score of Parentheses

String

Stack

Math

Problem Statement:

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

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

Approach:

1. Maintain a balance variable bal to track the depth of nested parentheses.
2. Iterate through the string, increasing bal for each '(' and decreasing it for each ')'.
3. Whenever a '(' is followed by a ')' (i.e., S[i-1] == '('), calculate the score for that pair as 1 << bal.
   • This works because the score doubles with each level of nesting, which can be represented as a left shift.
4. Add the computed score to the result variable ans.

Complexity:

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use variables to track balance and score.

Java Implementation:

public int scoreOfParentheses(String S) {
    int ans = 0, bal = 0;
    for (int i = 0; i < S.length(); ++i) {
        if (S.charAt(i) == '(') {
            bal++; // Increment balance for opening parenthesis
        } else {
            bal--; // Decrement balance for closing parenthesis
            // If a complete "()" is found, add score based on depth
            if (S.charAt(i-1) == '(') 
                ans += 1 << bal; // Score doubles with each level of nesting
        }
    }
    return ans;
}