Last Updated: 3 Jun, 2021

Minimum number of swaps

Moderate

Asked in company

Solve now

Problem statement

You are given a string ‘S’ of length ‘N’, an array A of length ‘M’ ( consisting of lowercase letters). and a positive integer ‘K’. You can take a character from 'A' and change any character in 'S' with this character. The task is to minimize the number of swaps required ( between ‘S’ and ‘A’ ) to make the string ‘S’ ‘k’-periodic.

Note:

1. A string ‘S’ is said to be ‘K’ periodic, if for each position  ‘i’ in the string S[i] = S[i+K].

   Consider string ‘S’,
   if S = ”abcabc”, it is 3 periodic string.
   if S= ”aaaaa”,  it is 1 periodic string.

2. In one move, only one character of ‘S’ can be swapped with a character of ‘A’.

3. The characters in ‘A’ can be used more than once.

4. All characters of K-periodic string ‘S’ are elements of array ‘A’.

Input Format:

 First-line will contain an integer ‘T’, the number of test cases. Then the test cases follow-

 Each test case contains three lines of input. 

 The first line contains three integers ‘N’, ‘M’, ‘K’. The second line contains a string of length ‘N’. 

 The third line contains ‘M’ space-separated smaller case letters.

Output Format:

For each test case output an integer i.e minimum number of swaps required to make string K-periodic.

Constraints:

1 <= T <= 5
1 <= N, M <= 2 * 10 ^ 4
1 <=  K < = N

Time limit: 1 sec.

Solve now

Approaches

01 Approach

Use a 2-dimensional array ‘frequency[K][26]’, where frequency[k][j] stores the frequency of characters ‘S[i]’ which lies in the series of index ‘k’ in K-periodic string, where ‘j’ = ‘i’ % ‘K’ for all 0 <= ‘i’ < N. And swap all the characters except the character which occurred maximum times in the series of ‘k-th’ index.

Algorithm :

Let ‘N’, ‘M’, ‘K’ be the length of string, length of a character array, and k-period value.
Let ‘S’ be the given string of length ‘N’ of the string.
Let ‘arr‘ be the given array of small letters of length ‘M’.
Maintain a ‘flag[26]‘ array, where index 0 represents ‘a’,1 represents ‘b’, and so on. Initialize it to false
Now loop for ‘i’ through ‘arr’ from 0 to ‘m’ - 1.
- Mark flag[arr[i] - ’a’] = 1.
Initialize the frequency[K][26] with 0.
Now loop through string ‘S’ from 0 to ‘N’.
- Increment the value of frequency[i % K][S[i] - ’a’] by 1
Let ‘ans’ store the answer( minimum number of swaps) initialized to 0.
Now loop for ‘i’ from 0 to K - 1.
- Maintain a variable ‘mx’ initialized to 0 which stores the maximum frequency of character in series of ‘i-th’ index from string
- Maintain 'totalCount' initialized to 0 which counts the total number of characters in the ‘k-th’ index.
- Loop for j from 0 to 25.
  - Update totalCount+=frequency[i][j]
  - If frequency[i][j] is greater than current maximum i.e ‘mx’ and flag[j]==1(character is present in given ‘arr’)
- update the ‘mx’ value as 'mx' = frequency[i][j]
- Update the ‘ans’ as ‘ans’ += ('totalCount' - ‘mx’)
Finally return the answer ‘ans’.

Solve now