Minimum number of swaps

Moderate
0/80
profile
Contributed by
7 upvotes
Asked in company
Amazon

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’.
Detailed explanation ( Input/output format, Notes, Images )
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.

Hint

Use frequency of characters in a given string

Approaches (1)
Frequency counting and Hashing

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’.
Time Complexity

O(max( N, M )), Where ‘N’ and ‘M’ are sizes of a given string and array.

 

The major task done in this algorithm is calculating the frequency of characters of string ‘S’ that takes O( N ) time. Initializing the flag that takes O( M )  and in the last loop, we are updating ‘mx’ for each k, that takes O( K * 26 ). Hence the Overall time complexity = O( N ) + O( M ) + O( K ) = O(max(N, M )) as 1 <= 'K' <  'N'.

Space Complexity

O( N ), where 'N' is the length of string ‘S’.

 

The major space we are using is flag array, which is O( 26 ) = O( 1 ), and 2D frequency array which is O( K * 26 ) = O( K ) hence, the overall time complexity is O(1 ) + O( K ) = O( N ) ,  where '1' <= ‘K’ < ‘N’.

Code Solution
(100% EXP penalty)
Minimum number of swaps
Full screen
Console