Problem Description

You are given a balanced parentheses string s consisting only of ( and ) characters. Your task is to calculate the score of this string based on specific scoring rules.

The scoring rules are:

• The basic unit "()" has a score of 1
• When two balanced parentheses strings A and B are placed side by side (concatenated), the total score is A + B
• When a balanced parentheses string A is wrapped by an outer pair of parentheses like (A), the score becomes 2 * A

For example:

• "()" has score 1 (base case)
• "(())" has score 2 (the inner () has score 1, wrapped by outer parentheses gives 2 * 1 = 2)
• "()()" has score 2 (two () side by side gives 1 + 1 = 2)
• "(()(()))" has score 6 (breaking it down: inner left () contributes 2, inner right (()) contributes 4, giving 2 + 4 = 6)

The key insight is that every () pair contributes to the final score, and its contribution is multiplied by 2^d where d is the depth (number of outer parentheses surrounding it). The solution tracks the depth as it iterates through the string, incrementing for ( and decrementing for ). When it encounters a () pair (detected when current character is ) and previous is (), it adds 2^d to the total score using bit shifting (1 << d).

Intuition

The key observation is that only the innermost () pairs actually contribute to the score - everything else is just a multiplier. Think about it: (()) is really just () with an extra layer that doubles its value. Similarly, ((())) is () with two extra layers that multiply its value by 4.

Let's trace through an example to see the pattern. Consider (()(())):

• The first () at positions 1-2 is at depth 1 (one unclosed ( before it), so it contributes 2^1 = 2
• The second () at positions 4-5 is at depth 2 (two unclosed ( before it), so it contributes 2^2 = 4
• Total score: 2 + 4 = 6

This matches what we'd get by manually applying the rules: (()(())) = (() + (())) = 2*1 + 2*2 = 6.

The brilliant insight is that we don't need to parse the entire structure or build a tree. We just need to:

1. Track our current depth (how many unmatched ( we've seen)
2. Whenever we see a () pair (which happens when current char is ) and previous was (), add 2^depth to our answer
3. The depth naturally accounts for all the outer parentheses that would multiply this basic unit

Why does 2^depth work? Because each level of nesting doubles the score. If a () is wrapped by n layers of parentheses, its contribution gets doubled n times, giving us 1 * 2 * 2 * ... * 2 (n times) = 2^n.

This transforms a potentially complex recursive problem into a simple linear scan with a depth counter - elegant and efficient!

Learn more about Stack patterns.

Solution Approach

The implementation uses a single-pass linear scan with a depth counter to calculate the score efficiently.

Algorithm Steps:

1. Initialize variables:

   • ans to store the cumulative score (starts at 0)
   • d to track the current depth of parentheses (starts at 0)

2. Iterate through each character in the string along with its index:

   • When encountering '(': Increment the depth d += 1 (we're going one level deeper)
   • When encountering ')':
     • First decrement the depth d -= 1 (we're closing a parenthesis)
     • Check if the previous character was '(' (forming a () pair)
     • If yes, add 1 << d (which equals 2^d) to the answer

3. Return the accumulated score

Why the depth adjustment order matters:

• For '(': We increment depth before any calculation
• For ')': We decrement depth first, then check for () pairs

This ensures that when we find a () pair, the depth d represents the number of complete outer parentheses surrounding it.

Example walkthrough with "(()(()))":

Index: 0  1  2  3  4  5  6  7
Char:  (  (  )  (  (  )  )  )
Depth: 1  2  1  2  3  2  1  0

At index 2: ')' and s[1]='(' → add 1<<1 = 2
At index 5: ')' and s[4]='(' → add 1<<2 = 4
Final answer: 2 + 4 = 6

Data structures used:

• Only two integer variables for tracking state
• No additional data structures needed

Time and Space Complexity:

• Time: O(n) - single pass through the string
• Space: O(1) - only using constant extra space

The bit shift operation 1 << d is an efficient way to calculate 2^d, making the solution both elegant and performant.

Example Walkthrough

Let's trace through the string "(()(()))" step by step to see how the solution calculates a score of 6.

Initial state: ans = 0, depth = 0

Step-by-step iteration:

Position 0: '('
- Increment depth: depth = 1
- No scoring action

Position 1: '('  
- Increment depth: depth = 2
- No scoring action

Position 2: ')'
- Decrement depth: depth = 1
- Previous char s[1] = '(' → Found "()" pair!
- Add 2^1 = 2 to answer: ans = 2

Position 3: '('
- Increment depth: depth = 2
- No scoring action

Position 4: '('
- Increment depth: depth = 3
- No scoring action

Position 5: ')'
- Decrement depth: depth = 2
- Previous char s[4] = '(' → Found "()" pair!
- Add 2^2 = 4 to answer: ans = 6

Position 6: ')'
- Decrement depth: depth = 1
- Previous char s[5] = ')' → Not a "()" pair
- No scoring action

Position 7: ')'
- Decrement depth: depth = 0
- Previous char s[6] = ')' → Not a "()" pair
- No scoring action

Final answer: 6

The key insight illustrated here: only the two () pairs at positions 1-2 and 4-5 contribute to the score. The first pair has 1 outer layer (depth=1), contributing 2^1=2. The second pair has 2 outer layers (depth=2), contributing 2^2=4. Everything else just provides the multiplying structure.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s. The algorithm iterates through each character in the string exactly once using a single for loop with enumerate. Each operation inside the loop (comparison, increment/decrement, bit shift, and addition) takes constant time O(1). Therefore, the overall time complexity is linear.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size. The variables used are:

• ans: an integer to store the accumulated score
• d: an integer to track the current depth of nested parentheses
• i and c: loop variables from enumerate

No additional data structures like arrays, stacks, or recursive call stacks are used, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Depth Update Timing

A common mistake is updating the depth at the wrong time relative to score calculation, leading to incorrect results.

Incorrect Implementation:

def scoreOfParentheses(self, s: str) -> int:
    total_score = 0
    depth = 0
  
    for index, char in enumerate(s):
        if char == '(':
            depth += 1
        else:  # char == ')'
            # WRONG: Checking for "()" before updating depth
            if s[index - 1] == '(':
                total_score += 1 << depth  # depth is off by 1!
            depth -= 1
  
    return total_score

This calculates 2^(d+1) instead of 2^d for each () pair because the depth hasn't been decremented yet.

Solution: Always decrement depth BEFORE calculating the contribution of a () pair.

2. Index Out of Bounds Error

When checking s[index - 1], the code assumes index > 0. While this works for valid balanced parentheses (which never start with )), it's fragile.

Defensive Implementation:

def scoreOfParentheses(self, s: str) -> int:
    total_score = 0
    depth = 0
  
    for index, char in enumerate(s):
        if char == '(':
            depth += 1
        else:  # char == ')'
            depth -= 1
            # Add boundary check for safety
            if index > 0 and s[index - 1] == '(':
                total_score += 1 << depth
  
    return total_score

3. Using Power Operation Instead of Bit Shift

While 2**depth and pow(2, depth) work correctly, they're less efficient than bit shifting.

Less Efficient:

total_score += 2 ** depth  # Works but slower

Better: Use 1 << depth for optimal performance, especially with larger depths.

4. Misunderstanding the Depth Concept

Some might think depth should start at 1 when entering the first (, but depth represents the number of COMPLETE outer parentheses surrounding a () pair.

Wrong Mental Model:

• Thinking depth = 1 inside first parenthesis
• This would make "()" contribute 2^1 = 2 instead of 2^0 = 1

Correct Understanding:

• Depth = 0 means no outer parentheses around the current () pair
• Each complete outer layer adds 1 to the depth