Problem

Submissions

Hints & solutions

Discuss

Score of Parentheses

Moderate

0/80

Average time to solve is 15m

Contributed by

7 upvotes

Asked in companies

Problem statement

One day Ninja goes to play some intellectual games. There was a game where Ninja is given a string of balanced parentheses 'STR' and he has to calculate the score of that using the given rules of the game. If he wins that game, the amount which he has paid for that game will be refunded.

Rules for the game are as follows:

For “()” you get a score of 1.
For “x y” you get a score of x + y where x and y are individual pairs of balanced parentheses.
For “(x)” you get a score twice of x (i.e), 2 * score of x.

Your task is to find the score using these rules for the given string 'STR'.

Example :

Suppose given string 'STR' is “( ( ) )”.
So we return ‘2’ as input is of the form “(x)”, therefore total score = 2 * score of “()” = 2 * 1 = 2.

Note :

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ representing the length of the string.

The second line of each test case contains a string ‘STR’ containing the balanced parentheses.

Output Format :

For each test case, return the score of the string using the rules given.

Constraints :

1 <= T <= 50
1<= |STR| <= 1000
STR[I] = { ‘(‘, ‘)’ }

Where ‘T’ represents the number of test cases and ‘STR’ represents the given string.

Time Limit: 1 second

Sample Input 1 :

2
4
()()
6
(()())

Sample Output 1 :

2
4

Explanation of Sample Input 1 :

Test Case 1 :

For the first test case, the given string 'STR' is “( ) ( )”. As 'STR' is in the form 'x + y', so we return ‘2’ as the score we get is 1 + 1 = 2.


Test Case 2 :

For this test case, the given string 'STR' is “( ( ) ( ) )”. So we return ‘4’ as the score we get is 2 * ( 1 + 1 ) = 4 as it is in the form '(x + y)'.

Sample Input 2 :

2
2
()
8
(()(()))

Sample Output 2 :

1
6

Explanation of Sample Input 2 :

Test Case 1 :

For the first test case, the given string 'STR' is “( )”. So we return ‘1’ as only one balanced parenthesis is present.


Test Case 2 :

For this test case, the given string 'STR' is “( ( ) ( ( ) ) )”. As 'STR' is in the form '( x + ( y ) )', so we return ‘6’ as the score we get is 2 * ( 1 + 2 * (1) ) = 6.

Hint 1

Hint 2

Can you think of a recursive approach?

Approaches (2)

Approach 1

Approach 2

Recursive Approach

The idea here is to use the recursion. If we encounter any ‘(‘ bracket and then ‘)’ bracket, we simply increase the score. Else if we found another ‘(‘ bracket, we call the recursively the same function and multiply the output by ‘2’ as for the nested parenthesis like ‘( ( ) )’, the answer will be 2 * score. In this way, we proceed to get our final answer.

We make a new function helper which takes input ‘STR’, ‘N’, and a variable ‘i’ which is passed as a reference.
Now we call this function. In this function we :
Run a loop while ‘i’ < length('STR').
- Now we check:
  - If ‘STR[i] == ‘(‘
    - If ‘STR[++i] == ‘)’
      - ‘ANS++’
      - i++
    - Else we call our recursive function as nested parenthesis like ‘( ( ) )’ can be there and multiply the score obtained by 2.
      - ANS = ANS + 2 * helper(STR, N , i)
  - Else
    - Return ‘ANS’.

Time Complexity

O(N), where ‘N’ is the size of the string.

As we are iterating through our string one time so complexity becomes O(N) time.

Space Complexity

O(N), where ‘N’ is the size of the string.

As recursion uses a stack space of size ‘N’ for storing recursive calls.

(100% EXP penalty)

Score of Parentheses

Ayush Gupta

Interview problems

C++ || Easy Solution

#include <bits/stdc++.h> 
int ninjaParentheses(string s, int n) {
	int ans=0;
	stack<int> st;
	for(auto x: s) {
		if(x=='(') {
			st.push(ans);
			ans=0;
		} else {
			ans=st.top()+max(2*ans, 1);
			st.pop();
		}
	}
	return ans;
}

53 views

0 replies

0 upvotes

IIT

Interview problems

Java Solution

import java.util.* ;
import java.io.*; 
public class Solution {
    public static int ninjaParentheses(String str, int n) {
        // Write your code here.
        Stack<Integer> st = new Stack<>();
        for(int i = 0; i < n ; i++){
            char ch = str.charAt(i);
            if(ch == '(')st.push(0);
            else if(ch == ')'){
                if(st.peek() == 0){
                    st.pop();
                    st.push(1);
                }else{
                    int sum =0;
                    while(st.peek() != 0){
                        sum += st.pop();
                    }
                    st.pop();
                    st.push(2*sum);
                }
            }
        }
        int res = 0;
        while(!st.isEmpty()){
            res += st.pop();
        }
        return res;

    }

}

22 views

0 replies

0 upvotes

Teena Goyal

Interview problems

c++ solution

#include <bits/stdc++.h>

int ninjaParentheses(string str, int n)

{

// Write your code here.

int depth = 0, res = 0;

char prev = '(';

for (char ch: str) {

if (ch == '(')

depth++;

else {

depth--;

if (prev == '(')

res += pow(2, depth);

}

prev = ch;

}

return res;

}

40 views

0 replies

0 upvotes

Imran Wahid

Interview problems

Easy C++ solution

#include <bits/stdc++.h> 
int ninjaParentheses(string str, int n) {
	int ans=0;
	stack<pair<int,int>>stk;
	// first -- index;
	// second -- score;
	for(int i=0;i<str.length();i++) {
		if(str[i]=='(') {
			stk.push({i,0});
		}
		else {
			auto node=stk.top();
			stk.pop();
			if(node.first==i-1) {
				if(stk.empty()) {
					ans++;
				}
				else {
					stk.top().second++;
				}
			}
			else {
				int score=node.second*2;
				if(stk.empty()) {
					ans+=score;
				}
				else {
					stk.top().second+=score;
				}
			}
		}
	}
	return ans;
}

146 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | Score of Parentheses

Hey everyone, creating this thread to discuss the interview problem - Score of Parentheses.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Score of Parentheses

103 views

2 replies

0 upvotes

Console