Last Updated: 3 Feb, 2021

Minimum Number Of Swaps For Bracket Balancing

Moderate

Asked in companies

Solve now

Problem statement

Ninja and his friend are playing a game in which his friend picks N opening brackets ‘(‘ and N closing brackets ‘)’. He then mixes all of them randomly and generates a string 'BRACKETS'. He asks Ninja to balance ‘BRACKETS’.

Example:

Here are some examples of balanced BRACKETS "(())", "()()", "(())()".

Ninja can perform the following operation to balance BRACKETS. In one operation, Ninja can pick two adjacent brackets and swap them. His friend challenges him to accomplish the task in minimum possible operations. Ninja needs your help to do this.

Can you help Ninja to make the string ‘BRACKETS’ balanced in minimum possible swaps?

Input Format:

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains one integer ‘N’ representing the number opening (or closing) brackets.

The second line of each test case contains a string‘ BRACKETS’ of length '2*N'.

Output Format :

For each test case, print the minimum possible swaps required to make string ‘BRACKETS’ balanced.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’ <= 5000 
‘BRACKETS’[i]’ = ‘(‘ or ‘)’

Time Limit: 1 second

Solve now

Approaches

01 Approach

We apply a greedy approach to balance ‘BRACKETS’. If the first ‘X’ characters form a balanced string, then we neglect these characters. And we maintain a ‘count’ variable. If we encounter an open ‘(‘ bracket then we increase our ‘count’ by ‘1’ else we decrease the ‘count’ by ‘1’. If the ‘count’ is negative, then we start balancing ‘BRACKETS’.

For balancing ‘BRACKETS’, we first store the current position say ‘i’, and then find the position of next ‘(‘ say ‘j’. We then swap the characters present at these positions. We also add ‘j’ - ‘i’ in our answer. We repeat this process until ‘BRACKETS’ is not balanced. In the end, we return our required answer.

Here is the algorithm :

We declare ‘minSwaps’ and ‘count’ for storing the resultant answer and for counting the difference of open and closed brackets, respectively.
We run a loop for ‘i’ = ’0’ to ‘N’:
- If the current character is ‘(‘:
  - ‘count++’
- Else:
  - ‘count--’
- If ‘count’ is negative then we start balancing ‘BRACKETS’:
  - We declare a variable ‘j’ which is used to find the position of next ‘(‘ and we initialize ‘j’ = ‘i’ + ‘1’.
  - We run a loop while ‘j’ < ‘N’ and ‘STR[j]’ = ‘)’.
    - ‘j++’
  - ‘minSwaps’ += ‘j’ - ‘i’
  - We run a loop while ‘j’ > ‘i’:
    - ‘BRACKETS’[j]’ = ‘BRACKETS’[j-1]’
    - ‘j--’
  - ‘BRACKETS’[i]’ = ‘(‘
  - ‘count’ = ‘1’
Finally, we return ‘minSwaps’ as our answer.

Solve now

02 Approach

In this approach, we make a list ‘posOfLeftBracket’ and store all positions of ‘(‘. We then take the variable ‘i’ which is used to indicate the next position of ‘(‘. We also maintain a ‘count’ variable and update it as mentioned in the previous approach. If the ‘count’ is negative, then we have to start balancing the string.

We swap the current index and ‘posOfLeftBracket[i]’ and add ‘posOfLeftBracket[i]’ - ‘i’ in ‘minSwaps’. We then reset the ‘count’ to ‘1’ and ‘i’ to ‘i+1’.

Here is the complete algorithm :

We declare a list ‘posOfLeftBracket’ in which we store all positions of ‘(‘.
We run a loop for ‘i’ = ‘0’ to ‘2N’:
- If ‘BRACKETS[i]’ == ‘(‘
  - ‘posOfLeftBracket.add(i)’
We declare the variables ‘count’, ‘i’ and ‘minSwaps’.
We run a loop for ‘j’ to ‘N’:
- If ‘BRACKETS[j]’ == ‘(‘ :
  - ‘count++’
  - ‘i++’
- Else:
  - ‘count--’
- If ‘count’ < ‘0’:
  - ‘minSwaps’ += ‘posOfLeftBracket[i]’ - ‘j’
  - tmp = ‘BRACKETS[i]’
  - ‘BRACKETS[i]’ = ‘BRACKETS[posOfLeftBracket[i]]’
  - ‘BRACKETS[posOfLeftBracket[i]]’ = tmp;
  - ‘i++’
  - ‘count’ = ‘1’
Finally, we return ‘minSwaps’.

Solve now