Last Updated: 4 Feb, 2021
Minimum Cost To Make String Valid
Moderate
Asked in companies
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.
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
Approaches
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.
- Initialize a counter ‘cnt’ and iterate the ‘STR’ and do the following:
- 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’.
We can use a stack to solve this problem. This approach aims to first remove valid parts of ‘STR’. For example, if ‘STR’ is “}{{}{” we will remove the valid part “{}” from ‘STR’ and the remaining part will be “}{{”. If we observe, we can notice that after removing the valid part from ‘STR’, we will always get a string like “}}{{…{“, a string that has 0 or more number of ‘}’ comes before, 0 or more numbers of ‘{’. Now let the number of ‘{’ is ‘p’ and the number of ‘}’ is ‘q'. Then we will need (‘p’ + 1) / 2 + (‘q’ + 1 / 2) reversals.
We can remove the valid part using the stack.
The algorithm for this approach is the following:
- If the length of ‘STR’ is odd, it is impossible to make ‘STR’ valid. Because each ‘{’ must have a ‘}’ to pair up. Return -1.
- Iterate the ‘STR’ and for each index do the following:
- If ‘STR[i]’ = ‘}’ and the stack is not empty then do the following:
- If the top element of the stack is '{' then we will pop from the stack.
- Else we will push the ‘STR[i]’ into the stack.
- Else push ‘STR[i]’ into the stack.
- If ‘STR[i]’ = ‘}’ and the stack is not empty then do the following:
- Now we have removed the valid part from ‘STR’ and we have a string like “}}{{…{“ as explained above. Inside the stack, so we will pop out all the elements and count the number of ‘{’ and ‘}’. Take two variables ‘p’ and ‘q’ where ‘p’ denotes the number of ‘{’ and ‘q’ denotes the number of ‘}’ and do the following steps while the stack not gets empty:
- If the top element of the stack is ‘{’ then increase p by 1.
- If the top element of the stack is ‘}’ then increase q by 1.
- Finally return ((‘p’ + 1) / 2 + (‘q’ + 1) / 2) because half of the ‘{’ can make remaining ‘{’ valid and same for ‘}’.