Score of Parentheses (#856 Leetcode)

 

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

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

 

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

 

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.


In this problem, the rules and constraints are important. 

Based on the rules, the score is calculated as below: 

Rule 1:  "()" has score 1

This is self explanatory.  Here, () is balanced parentheses.Eg: () => 1

Rule 2:  AB has score A + B, where A and B are balanced parentheses strings.

A is '()' and similarly B is another '()'. Individual balanced parentheses score is calculated based on rule 2 which is addition. 

Eg 1: ()() => 1+1 => 2

Eg 2: ()()() => 1+1+1 => 3

Rule 3: (A) has score 2 * A, where A is a balanced parentheses string.

Nested parentheses is (A) where A is '()'. If a balanced parentheses found inside another parentheses, then multiply the score with 2.

Eg 1: (()) => (1)=> 2 * 1 => 2

Eg 2: ((())) => ((1)) => (2 * 1) => (2) => 2*2 => 4

Eg 3: (((()))) => (((1))) => ((2 * 1)) => (2) => (2*2) => (4) => 2*4 => 8


Let's focus on the constraints, 

  • 2 <= s.length <= 50
 s contains minimum of 2 characters and maximum of 50 characters. 

  • s consists of only '(' and ')'.
 s contains only either '(' and ')'. No other braces(angular, curly, brackets) are in s. 

  • s is a balanced parentheses string.

s always contains balanced parentheses. This means it has a minimum score of 1. 

Data Structure

The purpose is, while traversing the string, calculate the score. There are two actions have to be done simultaneously while traversing each character in the string. 

1. Traverse/iterate the characters in the string 's'

2. Calculate the score for each character,


Definitely the first character in the s is '(' since s has balanced parentheses. For example, if s contains ()() based on rule 2, then, 

s[0] =>   (  => score should be 0.  

s[1] =>   )  => score should be 1 as it is balanced now. 

  • At this point, I understand I need to keep track of the opening parenthesis. Then only, score can be calculated.
  • I also know after calculating the score, I don't want to care s[0] and s[1]. 
  • This means, s[0] should be stored if it is '(' but when s[1] is ')', it doesn't need to be stored rather score should be calculated. 

s[2] =>  (  => score should be still 1.  

  •  As per my above understanding, s[2] should be stored but the score should be accumulated with the current score which is 0.
s[3] =>  )  => score should be 2 as all the visited characters are balanced now. 
  •  Now, the score should be added as it is individual parentheses = 1 +1 


From this we learnt,  storing all the opening parentheses in the datastructure and removing it while encountering the closing parentheses is a good choice. 
As we focused on removing the last element,  it would be LIFO concept. So, use Stack. 

Also, our aim is to calculate the score iteratively but not storing the string s characters. So, let's store the score in the stack iteratively instead of the string characters. 

What if the string contains (())? 

I think when we focus on the rule 3, we can get the formula to calculate the score. Just look carefully, how the score formula is developed at each step. 

s[0] => ( => score should be 0. 

         Since the character is (, current score 0 will be pushed into the stack.  Score is calculated as 0. 

           score of the stack = 0

s[1] => (  => score should be 0. 

          Since the character is (, score  0 will be pushed into the stack. Current score is accumulated with previous score or top of the stack value. Now the score is  0. 

            score of the stack = top of the stack + 0

When character is (, then don't calculate the score at all. 

s[2] => )  => score should be 1. 

         Since the character is ), 0 will be popped out of the stack. Score is calculated as 1.  

            score of the stack = top of the stack + 1 

Now, the stack contains only ( which is s[0]

s[3] => )  => score should be 2. 

         Since the character is ), the last element s[0]'s score 0 will be popped out of the stack. Score is calculated as 2 * 1.  

           score of the stack = top of the stack + max (2, 1) 

If I multiply 2 with top of the stack, it will be multiplied on every step. That's not correct. 

What if the string contains ((()))? 

s[2] => (  => score should be 0. 

          Since the character is (, score  0 will be pushed into the stack. Current score is accumulated with previous score or top of the stack value. Now the score is  still 0. 

            score of the stack = top of the stack + 0

s[3] => )  => score should be 1. 

         Since the character is ), stack top element 0 will be popped out of the stack. Score is calculated as 1.  

            score of the stack = top of the stack + 1 

Now, the stack contains  (( which is s[0] & s[1]

s[4] => )  => previous score is 1, score should be 2. 

         Since the character is ), the last element s[1]'s score 0 will be popped out of the stack. Score is calculated as 2 * 1.  

           score of the stack = top of the stack + max (2, 1) 

s[5] => )  => previous score is 2, current score is 1. score should be 4. 

         Since the character is ), the last element s[0]'s score 0 will be popped out of the stack. Score is calculated as 2 * 1.  

           score of the stack = top of the stack + max (2* previous score, 1) 

Here, previous score is nothing but the score of the stack. 

Now, dry run this formula for the rule 2 too. 


class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        int score = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){
                st.push(score);
                score = 0;
            }
            else {
                score = st.top() + max(2 * score, 1);
                st.pop();
            }
        }
        return score;
    }
};



Reference: 

https://leetcode.com/problems/score-of-parentheses/discuss/1856519/JavaC%2B%2B-Visually-Explained!!

Comments

Post a Comment