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. ”()” has score 1.
  2. AB has score A + B, where A and B are balanced parentheses strings.
  3. (A) has score 2 * A, where A is a balanced parentheses string.

Clarifying Questions

  1. What should we return if the string is empty?
    • Given the problem constraints, the input S is guaranteed to be a balanced parentheses string, so this is not a concern.
  2. Can the string contain any characters other than ( and )?
    • No, the string only contains ( and ) and it is guaranteed to be balanced.

Strategy

We can solve the problem using a stack to keep track of the scores. The idea is to maintain a stack where we push the current score of the parentheses at each depth level.

  1. Iterate through the given string S.
  2. Use a stack to maintain scores at each nested level.
  3. For every opening bracket (, push a 0 onto the stack indicating a new score level.
  4. For every closing bracket ), pop from the stack:
    • If the popped value is 0, it indicates a “()”, hence we push 1 onto the stack.
    • Otherwise, calculate 2 * score of the popped value and add the calculated score to the new top value of the stack.
  5. After processing all characters in the string, the top value of the stack will be the final score of the given balanced parentheses string.

Code

import java.util.Stack;

public class ScoreOfParentheses {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);  // The score of the current frame

        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                stack.push(0);  // Start a new frame
            } else {
                int v = stack.pop();  // Score of the inner frame
                int top = stack.pop();
                stack.push(top + Math.max(2 * v, 1));
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        ScoreOfParentheses solution = new ScoreOfParentheses();
        System.out.println(solution.scoreOfParentheses("()")); // Output: 1
        System.out.println(solution.scoreOfParentheses("(())")); // Output: 2
        System.out.println(solution.scoreOfParentheses("()()")); // Output: 2
        System.out.println(solution.scoreOfParentheses("(()(()))")); // Output: 6
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the given string S. This is because we process each character in the string exactly once.

The space complexity is also O(n) due to the usage of the stack, which in the worst case can grow to store all the nested levels of parentheses.

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