Minimum Cost To Make String Valid

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
264 upvotes
Asked in companies
MicrosoftAdobeAmazon

Problem statement

Ninja has been given a string ‘STR’ containing either ‘{’ or ‘}’. 'STR’ is called valid if all the brackets are balanced. Formally for each opening bracket, there must be a closing bracket right to it.

For Example: 
“{}{}”, “{{}}”, “{{}{}}” are valid strings while “}{}”, “{}}{{}”, “{{}}}{“ are not valid strings.

Ninja wants to make ‘STR’ valid by performing some operations on it. In one operation, he can convert ‘{’ into ‘}’ or vice versa, and the cost of one such operation is 1.

Your task is to help Ninja determine the minimum cost to make ‘STR’ valid.

For Example: 
Minimum operations to make ‘STR’ =  “{{“ valid is 1.

In one operation, we can convert ‘{’ at index ‘1’ (0-based indexing) to ‘}’. The ‘STR’ now becomes "{}" which is a valid string.

Note: 
Return -1 if it is impossible to make ‘STR’ valid.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The only line of each test case contains a string 'STR'.
Output Format : 
For each test case, print the minimum cost needed to make ‘STR’ valid.

Print -1 if it is impossible to make ‘STR’ valid.

Print the output of each test case in a separate line.
Note : 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 100
0 <= |STR| <= 10^5
STR[i] = ‘{’ or ‘}’

Time Limit: 1 sec
Sample Input 1:
2
{{{}
{{}{}}
Sample Output 1:
1
0
Explanation For Sample Input 1:
For the first test case:
The two valid strings that can be obtained from  ‘STR’ using minimum operations “{{}}”   and “{}{}”. Ninja can transform ‘STR’ to “{{}}” by performing the following operations:
Convert ‘{’ at index 2 to ‘}’.

Ninja can transform ‘STR’ to “{}{}” by performing the following operations:
Convert ‘{‘ at index 1 to ‘}’.
The minimum number of operations in transforming ‘STR’ to either of the two valid strings is 1.So, the total cost is 1.

For the second test case:
Given ‘STR’ is already valid so the minimum number of 
operations required is 0.
So, the total cost is 0.
Sample Input 2:
3
{}}{}}
{{{{
{{{}}
Sample Output 2:
1
2
-1
Hint

Brute Force

Approaches (2)
Recursion

The idea for this approach is to consider every bracket and then recursively count the number of reversals.

 

We will have only two cases: either a bracket remains the same or converted to another. If we get a valid string, we will count the cost and update the minimum cost so far.

 

Algorithm:

 

Initialize a variable ‘minCostSoFar’ to maximum possible value, and call helper function minCostUtil which is a recursive function having parameters ‘index’ that denotes the current index in the ‘STR’, ‘currCost’ which is the cost to make string valid till ‘index’ and ‘minCostSoFar’ which denotes the minimum cost so far to make ‘STR’ valid.  

 

Implementation of minCostUtil is as follows :

 

  • If ‘index’ equals the length of ‘STR’, we will check if the string is valid or not using the function isValidString. If it is valid we will update ‘minCostSoFar’ as the minimum of ‘minCostSoFar’ and ‘currCost’. Function isValidString is :
    • Initialize a counter ‘cnt’ and iterate the ‘STR’ and do the following:
      • If ‘STR[i]’ = ‘{‘ then ‘cnt++’.
      • Else ‘cnt--’.
      • If at any step the ‘cnt’ becomes negative then ‘STR’ is not valid and return false.
    • Finally, if ‘cnt’ is 0 then return true. Else return false.
  • For each index do the following:
    • If ‘STR[index]’ is ‘{‘ then convert ‘STR[index]’ to ‘}’ and increase the cost by 1. We call this recursive function both by increasing ‘index’ by 1 and not changing the value and increasing ‘index’ by 1.
    • If ‘STR[index]’ is ‘}’ then convert ‘STR[index]’ to ‘{’  and increase the cost by 1. We call this recursive function both by increasing ‘index’ by 1 and not changing the value and increasing ‘index’ by 1.
  • Finally, we return ‘minCostSoFar’.

  

Time Complexity

 O(|STR| * 2^|STR|) where |STR| denotes the length of string ‘STR’.

 

Because each recursive call is invoking further 2 recursive calls and in each call, we are checking if ‘STR’ is valid or not in O(|STR|). So, the size of the recursive tree will be of order O(2^|STR|). Hence overall time complexity will be O(|STR| * 2^|STR|).

Space Complexity

O(|STR|) Where |STR| is the length of ‘STR’

 

Because recursive stack will have size equal to the length of ‘STR’

Code Solution
(100% EXP penalty)
Minimum Cost To Make String Valid
Full screen
Console