 3

# Minimum number of swaps

Difficulty: MEDIUM

Problem Statement
Suggest Edit

#### 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.
``````
##### Sample Input 1:
``````2
7 3 3
abcbbde
a b c
5 2 2
ninja
n i
``````
##### Sample Output 1:
``````3
2
``````
##### Explanation:
``````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:
``````1
3 1 1
aaa
a
``````
##### Sample Output 2:
``````0
``````
##### Explanation:

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