Last Updated: 9 Nov, 2021

Minimum Swaps

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

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

Solve now

02 Approach

In this approach, we will traverse the whole string ‘S’ and find the number of opening brackets that are not matched with a closing bracket. Let that number is ‘X’, so the number of swaps required is (X+1)/2, as we have seen in approach-1 that one swap can reduce the number of unused opening brackets by 2.

For example if S = “]]]][[[[“ and here the number of unused opening brackets is 4.If we swap the first and last character of the string, the resultant string will be ‘[]]][[[]’ whose number of unused opening brackets is2.

At last, we will return (‘X’+1)/2.

Algorithm:

Declare ‘X’ to store the number of unused opening brackets.
Set ‘X’ as 0.
For ‘ch’ in ‘S’, do the following:
- If ‘ch’==’[’:
  - Set ‘X’ as ‘X’+1.
- Else:
  - If X>0:
    - Set ‘X’ to ‘X’-1.
Set ‘ANS’ as (X+1)/2.
Return ‘ANS’.

Solve now