Count the Reversals

Given a string S consisting only of opening and closing curly brackets '{' and '}' find out the minimum number of reversals required to make a balanced expression.

Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases
follow. The first line of each test case contains a string S consisting only of { and }.

Output
Print out minimum reversals required to make S balanced. If it cannot be balanced, then print -1.

Constraints
1 <= T <= 100
0 <= |S| <= 50

Examples
Input
4
}{{}}{{{
{{}}}}
{{}{{{}{{}}{{
{{{{}}}}

Output
3
1
-1
0

Explanation:
Testcase 1: For the given string }{{}}{{{ since the length is even we just need to count the number of openning brackets('{') suppose denoted by 'm' and closing brackest('}') suppose dentoed by 'n' after removing highlighted ones. After counting compute ceil(m/2) + ceil(n/2).




Comments

Post a Comment

Popular posts from this blog

  Count numbers containing 4   Basic  Accuracy:   48.18%  Submissions:   2010  Points:   1 Count the numbers between 1 to  N  containing 4 as a digit.   Example 1: Input: N = 9 Output: 1 Explanation: 4 is the only number between 1 to 9 which contains 4 as a digit. Example 2: Input: N = 14 Output: 2 Explanation: 4 and 14 are the only number between 1 to 14 that contains 4 as a digit.   Your Task: You don't need to read input or print anything. Your task is to complete the function  countNumberswith4()  which takes an Integer N as input and returns the answer.
Read more

Change Bits

Easy  Accuracy:   72.48%  Submissions:   1390  Points:   2 Given a number  N,  complete the following tasks, Task 1. Generate a new number from N by changing the zeroes in the binary representation of N to 1. Task  2. Find the difference between N and the newly generated number.   Example 1: Input: N = 8 Output: 7 15 Explanation: There are 3 zeroes in binary representation of 8. Changing them to 1 will give 15. Difference between these two is 7. Example 2: Input: N = 6 Output: 1 7 Explanation: There is 1 zero in binary representation of 6. Changing it to 1 will give 7. Difference between these two is 1.   Your Task: You don't need to read input or print anything. Your task is to complete the function  changeBits()  which takes an integer N as input parameter and returns a list of two integers containing the difference and the generated number respectively.
Read more