algoadvance

Leetcode 856. Score of Parentheses

Problem Statement

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

  1. (): Provides a score of 1.
  2. AB: Where A and B are balanced parentheses strings, the score is A + B.
  3. (A): Where A is a balanced parentheses string, the score is 2 * A.

Example:

Clarifying Questions:

  1. Can the input string be empty?
    • No, the input will always be a non-empty string.
  2. Is the input guaranteed to be a balanced parentheses string?
    • Yes, the input is always a balanced parentheses string.

Strategy:

We can solve this problem using a stack to help manage the nested structure of the parentheses.

Here’s the step-by-step strategy:

  1. Initialize a stack to keep track of the scores.
  2. Traverse the string character by character.
  3. When encountering (:
    • Push a marker or 0 onto the stack. This marker indicates the beginning of a new score calculation.
  4. When encountering ):
    • Pop elements off the stack until encountering a marker.
    • Calculate the score for the current balanced substring based on the rules given.
    • Either () which contributes 1 or (A) which contributes 2 * A.
    • Push this score back to the stack to be added to any outer score.
  5. Sum up all values left in the stack to compute the total score.

Time Complexity:

The algorithm processes each character of the string exactly once. Hence, the time complexity is O(n), where n is the length of the string.

Code:

#include <iostream>
#include <stack>

int scoreOfParentheses(const std::string& S) {
    std::stack<int> stack;
    for (char c : S) {
        if (c == '(') {
            stack.push(0); // Use 0 as a marker for '('
        } else {
            int currentScore = 0;
            while (stack.top() != 0) {
                currentScore += stack.top();
                stack.pop();
            }
            stack.pop(); // remove the 0 marker
            // If `currentScore` is 0, it means we just closed `()`, score is `1`
            // Otherwise, `(A)` contributes `2 * A`
            stack.push(currentScore == 0 ? 1 : 2 * currentScore);
        }
    }

    int totalScore = 0;
    while (!stack.empty()) {
        totalScore += stack.top();
        stack.pop();
    }

    return totalScore;
}

int main() {
    std::string s = "(()(()))";
    std::cout << "Score of Parentheses: " << scoreOfParentheses(s) << std::endl;
    return 0;
}

This code should correctly compute the score for any balanced parentheses string, following the rules provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI