Score of Parenthesis LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Facebook Google Infosys VMware
Stack String tiktokViews 1798

Problem Statement

The score of Parenthesis LeetCode Solution says –

Given a balanced parentheses string s and return the maximum score.

The score of a balanced parenthesis string is based on the following rules:

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

 

Example 1:

Input:

 s = "()"

Output:

 1

Example 2:

Input:

 s = "(())"

Output:

 2

Example 3:

Input:

 s = "()()"

Output:

 2

 

Constraints – 

  • s is a balanced parenthesis string.
  • s only contains “(” and “)”.

 

Algorithm –

IDEA –

– In order to find the Score of Balanced Parenthesis. What we will do in this question. At first, we will focus on the balanced parenthesis if they are balanced then the count will be 1.

  • if the balanced parenthesis is inside the balanced parenthesis then our answer will be 2*balanced parenthesis. so first we will create one stack and one answer variable = 0.
  • after that will iterate through the whole string if i == “(” then we will push the answer into the stack and update the answer as 0.
  •  if i == “)” then we will check for the answer variable if it is zero then we will update answer = 1 else will update the answer as 2* answer and add the last element of the stack into the answer.

 

Approach –

– Create one stack and one variable and set it as 0.

– Iterate through the string and check for the condition if i == “(“. Then append variable into stack and update variable = 0.

–  if i = “)” then will check for two condition if variable != 0 then update variable as variable = 2*variable else variable = 1 and at last add the popped element in variable.

  • Hence we will calculate the Score Of Parenthesis.

Score of Parenthesis LeetCode Solution

 

Code:

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        
        for(char i:s.toCharArray()){
            
            if(i == '('){
                stack.push(ans);
                ans = 0;
                
            }
            else if(i == ')'){
                
                if(ans != 0)
                   ans = 2*ans;
                else
                    ans = 1;
                
                ans += stack.pop();
                            
            }
               
        }
        
        return ans;
        
        
        
    }
    
}
class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []
        ans = 0
        
        for i in s:
            if i == "(":
                stack.append(ans)
                ans = 0
                
            elif i == ")":
                if ans:
                    ans = 2*ans
                    
                else:
                    ans = 1
                
                ans += stack.pop()
                
        return ans

Complexity Analysis of The Score of Parentheses Leetcode Solution:

Time complexity:

The Time Complexity of the above solution is O(N) as we have traversed the whole string only once.

Space complexity:

The Space Complexity of the above solution is O(N) as we have created one stack.

 

Some more questions related to stack – https://tutorialcup.com/interview/stack/check-for-balanced-parentheses-in-an-expression.htm

 

 

 

 

 

 

 

 

Translate »