Minimum number of swaps

Difficulty: MEDIUM

Problem Statement
Suggest Edit

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.


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.
1 <= T <= 5
1 <= N, M <= 2 * 10 ^ 4
1 <=  K < = N

Time limit: 1 sec.
Sample Input 1:
7 3 3
a b c
5 2 2
n i
Sample Output 1:
In first test case, We need at least 3 swaps to make the string “abcbbde” 3 periodic. One swap between characters at index 3 in string and letter ‘a’ from the array. Second swap between character at index 6 in string and letter ‘a’ from array Third swap between character at index 5 in string and letter ‘c’ from the array.
Sample Input 2:
3 1 1
Sample Output 2:

In total 0 swaps are required to make string ‘1’-periodic.

Reset Code
Full screen