algoadvance

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

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

Example:

• Input: S = "()" Output: 1

• Input: S = "(())" Output: 2

• Input: S = "()()" Output: 2

• Input: S = "(()(()))" Output: 6

Clarifying Questions

1. Input Constraints:
   • Is the input always a valid balanced parentheses string?
   • What is the maximum length of the string S?
2. Output Requirements:
   • Should the result be an integer score?

Let’s assume the string is always a valid balanced parentheses string and the length constraints are manageable within typical competitive programming limits.

Strategy

Given the rules, we can use a stack-based approach to compute the score:

1. Initialize: Create an empty stack to keep track of scores.
2. Traverse String S:
   • For each character in the string:
     • If we encounter '(', we push a marker (e.g., 0) onto the stack to denote the beginning of a new group.
     • If we encounter ')', we:
       • Pop elements from the stack until we encounter a marker (0). The popped elements are part of the same nested group and their sum corresponds to A in the rule (A) (score is 2 * A).
       • If the marker is popped immediately (i.e., no nested group within), treat it as a single pair () with a score of 1.
       • Otherwise, accumulate the nested score into 2 * A.
3. Final Result: Sum up all the elements remaining in the stack for the final score.

Time Complexity

The time complexity is O(n), where n is the length of the string S, since each character is processed a constant number of times (push and pop operations on the stack).

Code

def scoreOfParentheses(s: str) -> int:
    stack = []

    for char in s:
        if char == '(':
            stack.append(0)
        else:
            cur = stack.pop()
            if cur == 0:
                stack.append(1)
            else:
                acc = 0
                while cur != 0:
                    acc += cur
                    cur = stack.pop()
                stack.append(2 * acc)
    
    return sum(stack)

# Example Usage
print(scoreOfParentheses("()")) # Output: 1
print(scoreOfParentheses("(())")) # Output: 2
print(scoreOfParentheses("()()")) # Output: 2
print(scoreOfParentheses("(()(()))")) # Output: 6

Explanation

• We use a stack to handle nested structures effectively.
• Push 0 for an opening bracket (.
• On encountering ), calculate the score based on the stack contents:
  • If immediate top is 0, it’s a simple (), push score 1.
  • If the top is not 0, sum up all inner scores until hitting 0, double the result, and push it back.

This approach ensures that the nested structure’s scores are calculated correctly according to the rules provided.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?