How do you solve Score of Parentheses on LeetCode?

Score of Parentheses (LeetCode #856) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack helps manage nested structures effectively.

What is the brute force solution for Score of Parentheses?

The brute force approach for Score of Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible substrings of the balanced parentheses string and calculating their scores. This method is straightforward but inefficient, as it examines every possible combination. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Score of Parentheses?

Score of Parentheses uses the following concepts: String, Stack. The recommended patterns to study are: Stack, Recursion.

What are the interview tips for Score of Parentheses?

Explain your thought process clearly as you code. Practice writing both brute force and optimal solutions to understand trade-offs. Be prepared to discuss the time and space complexities of your solution.

What are common mistakes when solving Score of Parentheses?

Not handling nested parentheses correctly. Forgetting to reset the score when encountering a new '('.

#856

Score of Parentheses

Medium

StringStackStackRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a stack to keep track of the scores as we parse through the string. This method is efficient and leverages the structure of the parentheses to compute scores in a single pass.

⚙️

Algorithm

4 steps

1Step 1: Initialize a stack to hold scores and a variable for the current score.
2Step 2: Iterate through each character in the string.
3Step 3: For each '(', push the current score onto the stack and reset the score to 0.
4Step 4: For each ')', pop from the stack and update the score based on the popped value, doubling it if it was preceded by a '('.

solution.py10 lines

1def scoreOfParentheses(s):
2    stack = []
3    score = 0
4    for char in s:
5        if char == '(': 
6            stack.append(score)
7            score = 0
8        else:
9            score = stack.pop() + max(2 * score, 1)
10    return score

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once, and the space complexity is O(n) due to the stack used to store scores.

1Using a stack helps manage nested structures effectively.
2Understanding the scoring rules is crucial for implementing the logic correctly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.