Minimum Swaps

Moderate
0/80
1 upvote
Asked in companies
SamsungTwitterShareChat

Problem statement

Ninja is playing with a string ‘S’ consisting of only equal numbers of opening brackets ‘[’ and closing brackets ’]’. The string was initially balanced but due to Ninja’s friend’s mischief, the string got shuffled up. Now, Ninja wants to make the string balanced again using the minimum number of swaps. Can you help Ninja to find the minimum number of swaps required to make the string balanced again?

A string is called balanced if and only if:

1.It is the empty string, or 2.It can be written as AB, where both A and B are balanced strings, or 3.It can be written as [C], where C is a balanced string.

You are given a string ‘S’ having ‘N/2’ opening brackets and N/2 closing brackets. You have to find the minimum number of swaps required to make ‘S’ balanced again.

For Example 
If the given string S = “ [[]]][ ”, the answer will be 1 as if we swap the last and second last character, the string will be balanced.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of characters present in string S.

The following line contains the string ‘S’.
Output Format: 
For each test case, print ‘an integer corresponding to the minimum number of swaps required.

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 <= 10
1 <= N <= 10^6.
S[i] = { ‘[’ , ‘]’}.

Time limit: 1 sec
Sample Input 1:
2
6
[[]]][
6
]]][[[
Sample Output 1:
1
2
Explanation of sample input 1:
For the first test case,

The minimum number of swaps required is 1.
Swap 1: Swap S[5] and S[4].
The resultant string will be “[[[]]]” which is balanced. Hence, the answer is 1.


For the second test case:

The minimum number of swaps required is 2.
Swap 1: Swap S[0] and S[5].
Swap 2: Swap S[2] and S[3]
The resultant string will be “[][][]” which is balanced. Hence, the answer is 2.
Sample Input 2:
2
[]
6
][]][[
Sample Output 2:
0
1
Hint

Check for the character which should be swapped and select a suitable character with whom that will be swapped.

Approaches (2)
Two Pointers approach.

In this approach, we will declare two pointers ‘i’ and ‘j’ to traverse the string. ‘i‘ will be pointing to the first character and ‘j’ will be pointing to the last character. We will store the number of unused opening brackets in variable ‘C’. We will iterate ‘i’ from left to right, if we find any opening bracket, we will increment ‘C’ to  ‘C+1’. If we found a closing bracket, we will decrement ‘C’ to ‘C’-1 as one opening bracket will be used. If ‘C’ became -1, that implies the closing bracket should be swapped with an opening bracket. So, they will find the first opening bracket from the end using pointer ‘j’  and swap them and increment ‘ANS’ as ‘ANS+1’.

At last, we will return ‘ANS’ storing the minimum number of swaps required. 


 

Algorithm:

  • Declare two variables ‘i’ and ‘j’.
  • Declare ‘C’ to store the number of unused opening brackets.
  • Declare ‘ANS’ to store the minimum number of swaps required.
  • Set i to 0 and j to ‘N-1’.
  • Set ‘ANS’ to 0 and ‘C’ to 0.
  • While ‘i’ < ‘j’:
    • If S[i]==’[’ :
      • Set ‘C’ to ‘C’+1.
    • Else:
      • Set ‘C’ to  ‘C’-1.
    • If C<0:
      • We need to swap the i’th character,
      • Find the first opening bracket from the end.
      • While i<j and S[j]==’]’:
        • Set j  to  j-1.
      • We need to swap S[i] and S[j], so increase ans by one.
      • Set ‘ANS’ as ‘ANS’ +1.
      • Set ‘C’ as 1.
    • Set i as i+1.
  • Return ‘ANS’.
Time Complexity

O(N), where ‘N’ is the number of characters in string ‘S’.

 

In this approach, we traverse the whole string using two pointers, so the number of operations will be O(N). Hence, the overall time complexity is O(N).

Space Complexity

O(1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Swaps
Full screen
Console