Minimum Number Of Swaps For Bracket Balancing

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
OlaUnthinkable SolutionsNagarro Software

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?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
()
2
)(
Sample Output 1:
0
1

Explanation For Sample Output 1:

For sample test case 1: 
In this sample test case, the given input string is already balanced. So the minimum number of swaps required to balance ‘BRACKETS’ is 0.

For sample test case 2: 
In this sample test case, if we swap position 0 with 1, then the string ‘BRACKETS’ becomes "()" which is balanced. So, the minimum number of swaps needed to balance ‘BRACKETS’ is 1.
Sample Input 2:
2
3
())()(
2
))((
Sample Output 2:
 2
 3
Hint

Do we need to balance the part of BRACKETS that is already balanced? 

Approaches (2)
Greedy

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.
Time Complexity

O(N ^ 2)  Where ‘N’ is the number of opening (or closing) brackets in the string ‘BRACKETS’.

 

Because in the worst case (eg. if N = 3 and ‘BRACKETS’ = ")))(((" ) :

For i = 0, we run a loop ‘j’ = ‘0’ to ‘3’ and then again ‘3’ to ‘0’

For i = 1, we run a loop ‘j’ = ‘1’ to ‘4’ and then again ‘4’ to ‘1’

For i = 2, we run a loop ‘j’ = ‘2’ to ‘5’ and then again ‘5’ to ‘2’

For i = 3, we don’t run a loop for j.

For i = 4, we don’t run a loop for j.

For i = 5, we don’t run a loop for j.

 

So, in this case we perform (N^2 / 2 + N / 2) unit operations and we can neglect the N/2 part because N^2 is more dominant than N. Hence, the overall time complexity is O(N^2).

Space Complexity

O(1)

 

Because we are not using any extra space.

Code Solution
(100% EXP penalty)
Minimum Number Of Swaps For Bracket Balancing
Full screen
Console