algoadvance

Problem Statement

You have an interview problem typically called “Score of a String” where the specifics from the problem statement are as follows:

Given a string s of balanced parentheses, you need to calculate 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.

Clarifying Questions

To ensure clarity, we may ask the following clarifying questions:

• Can the input string be empty? (Assumption: No, it is always balanced and non-empty as per typical problem constraints).
• Are there any constraints on the length of the string? (This usually clarifies if a linear solution is preferred).
• Are there any special characters apart from ‘(‘ and ‘)’ in the input string? (Assumption: No).

Strategy

Given the problem constraints and the rules for scoring, we can use a stack to help calculate the score:

1. Use a stack to keep track of the scores at each level of nesting.
2. Iteratively process each character in the string.
   • If we encounter an ‘(‘, push 0 onto the stack to represent the start of a new balanced substring.
   • If we encounter a ‘)’, pop from the stack to get the score of the innermost substring. If the popped score is 0 (indicating a direct “()” pattern), add 1 to the current score. Otherwise, double the popped score and add to the current top of the stack.
3. The final score will be the value in the stack.

Code

Here’s the Python code implementing the described strategy:

def scoreOfParentheses(s: str) -> int:
    stack = [0]  # Initialize stack with 0 to handle outermost level score
    
    for ch in s:
        if ch == '(':
            stack.append(0)  # Push new score layer for the new '('
        else:
            v = stack.pop()  # Pop the last score (should be the score within current '()')
            if v == 0:
                v = 1  # An isolated '()' pattern contributes 1
            else:
                v *= 2  # 2 * inner_score for the pattern '(A)'
            stack[-1] += v  # Add calculated value to the previous level
            
    return stack.pop()  # Final score is at the top of the stack

# Example usage:
print(scoreOfParentheses("()"))           # Expected output: 1
print(scoreOfParentheses("(())"))         # Expected output: 2
print(scoreOfParentheses("()()"))         # Expected output: 2
print(scoreOfParentheses("(()(()))"))     # Expected output: 6

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string. Each character in the string is processed exactly once, and the stack operations (push and pop) are O(1). Hence, the algorithm runs in linear time.

Conclusion

This solution effectively uses a stack to handle the nested structure of the parentheses and calculate the score based on the described rules. It ensures that we can handle any valid balanced parentheses string in linear time.

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?