Minimum Cost To Make String Valid
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

Question

Minimum Cost To Make String Valid

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

Accepted Answer

Step 1 : I gave the most optimized approach with O(n) time complexity.
I shouldn't have done that. You should always start with the brute force approach and then optimize that.

Accepted Answer

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’.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: OtherExplanation:

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|).

Accepted Answer

Stack

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.
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 ‘}’.

Space Complexity: O(n)Explanation:

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

Because in the worst case stack will have size equals to the length of ‘STR’

Time Complexity: O(n)Explanation:

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

Because we are traversing each element in the ‘STR’ exactly once and popping out from stack once so we get O(|STR| + |STR|) which is equal to O(|STR|).

Python (3.5)

'''

    Time Complexity : O(|STR|)
    Space Complexity : O(|STR|)

    Where |STR| is the length of STR.

'''

from collections import deque

def findMinimumCost(str):
    n = len(str)
    
    # If lenght is odd then it is impossible to make str valid.
    if(n % 2 == 1):
        return -1

    # To store invalid parts.
    st = deque()

    for i in range(n):

        if(str[i] == '}' and len(st) != 0):

            if(st[len(st) - 1] == '{'):

                # Remove the valid part in the stack.
                st.pop()
            else:

                # Keep the invalid part in the stack.
                st.append(str[i])
        else:
            # Keep the invalid part in the stack.
            st.append(str[i])
    
    p, q = 0, 0

    # Calculate the opening and closing brackets
    while(len(st) != 0):

        if(st[len(st) - 1] == '{'):
            p += 1

        else:
            q += 1

        st.pop()

    return ((p + 1) // 2) + ((q + 1) // 2)

C++ (g++ 5.4)

/*
    Time Complexity : O(|STR|)
    Space Complexity : O(|STR|)

    Where |STR| is the length of STR.
*/

#include

int findMinimumCost(string str)
{
	int n = str.length();

	// If lenght is odd then it is impossible to make str valid.
	if (n % 2 == 1)
	{
		return -1;
	}

	// To store invalid parts.
	stack st;

	for (int i = 0 ; i < n ; i++)
	{
		if (str[i] == '}' && !st.empty())
		{
			if (st.top() == '{')
			{
				// Remove the valid part in the stack.
				st.pop();
			}
			else
			{
				// Keep the invalid part in the stack.
				st.push(str[i]);
			}
		}
		else
		{
			// Keep the invalid part in the stack.
			st.push(str[i]);
		}
	}

	int p = 0, q = 0;

	// Calculate the opening and closing brackets
	while (!st.empty())
	{
		if (st.top() == '{')
		{
			p++;
		}
		else
		{
			q++;
		}
		st.pop();
	}

	return ((p + 1) / 2) + ((q + 1) / 2);
}

Java (SE 1.8)

/*
    Time Complexity : O(|STR|)
    Space Complexity : O(|STR|)

    Where |STR| is the length of STR.
*/

import java.util.Deque;
import java.util.LinkedList;

public class Solution 
{
	public static int findMinimumCost(String str) 
	{
		int n = str.length();

		// If lenght is odd then it is impossible to make str valid.
		if (n % 2 == 1) 
		{
			return -1;
		}

		// To store invalid parts.
		Deque open = new LinkedList();
		Deque close = new LinkedList();

		int price = 0;

		for (int i = 0; i < str.length(); i++) 
		{
			if (str.charAt(i) == '}') 
			{

				if (open.isEmpty()) 
				{
					// Keep the invalid part in the stack.
					price++;
					open.add(str.charAt(i));
				} 
				else 
				{
					// Remove the valid part in the stack.
					open.removeLast();
				}

			} 
			else 
			{
				// Keep the invalid part in the stack.
				open.add(str.charAt(i));
			}


		}

		if (open.isEmpty()) 
		{

			if (close.size() % 2 == 1) 
			{
				return -1;
			} 
			else 
			{
				return (close.size() / 2) + price;
			}
		} 
		else 
		{

			if (open.size() % 2 == 1) 
			{
				return -1;
			} 
			else 
			{
				return (open.size() / 2) + price;
			}

		}
	}
}

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:

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:

Note:

Input Format :

Output Format :

Note :

Constraints :

Top Adobe Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern