Minimum number of swaps required to make the string K periodic
Given a string S of length N, and an array A, consisting of lowercase letters. Also given a positive integer K. the task is to find the minimum number of swaps required (between S and A) to make string S K periodic.
Note:
- A string is said to be K periodic if for each position i in the string S[i] = S[i+K].
- In one move, only one character of S can be swapped with a character of A.
- The characters in A can be used more than once.
Examples:
Input: S = “nihsiakyt”, K = 3, A = [‘n’, ‘i’, ‘p’, ‘s’, ‘q’]
Output: 6
Explanation:
Considering 0 based positioning for the string S:
Positions 3, 6 should be replaced with ‘n’.
Position 7 should be replaced with ‘i’.
Positions 2, 5, 8 can be replaced with any character from A to make the string K periodic.
Final 3 periodic string: “nisnisnis”
Therefore minimum swaps required = 6Input: S = “abcdeactr”, K = 4, A = [‘a’, ‘c’, ‘p’]
Output: 5
Explanation:
In total 5 changes are needed to make the string 4 periodic.
Approach: This problem can be solved with help of frequency counting and hashing.
- To solve the problem mentioned above we use a 2-dimensional array freq[K][26] to store frequency of characters at position j % K for all .
- Use a boolean array to mark all characters present in array A.
- For all characters in range 0 to K there will be N / K or (N / K + 1) characters which should be same.
- So for all such characters we check which character has the maximum frequency at position i and is also present in array A.
- Add that to the answer, i.e. .
- We will also add 1 to the answer if
- because there will be N / K + 1 characters for all such characters i.
Below is the implementation of above approach:
C++
// C++ code to find the minimum // number of swaps required to // make the string K periodic #include <bits/stdc++.h> using namespace std; int minFlip(string s, int n, int k, char a[], int p) { bool allowed[26] = { 0 }; for ( int i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a' ] = true ; } char freq[k][26]; // Initialize the freq array to 0 for ( int i = 0; i < k; i++) for ( int j = 0; j < 26; j++) freq[i][j] = 0; for ( int i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k][s[i] - 'a' ] += 1; } int ans = 0; // Total number of periods of // size K in the string int totalpositions = n / k; for ( int i = 0; i < k; i++) { int maxfrequency = 0; for ( int j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency and allowed[j] == true ) maxfrequency = freq[i][j]; } // update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the string // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } cout << ans << endl; } // Driver code int main() { string S = "nihsiakyt" ; int n = S.length(); int K = 3; char A[5] = { 'n' , 'i' , 'p' , 's' , 'q' }; int p = sizeof (A) / sizeof (A[0]); minFlip(S, n, K, A, p); return 0; } |
Java
// Java code to find the minimum // number of swaps required to // make the String K periodic import java.util.*; class GFG{ static void minFlip(String s, int n, int k, char a[], int p) { boolean allowed[] = new boolean [ 26 ]; for ( int i = 0 ; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a' ] = true ; } char [][]freq = new char [k][ 26 ]; // Initialize the freq array to 0 for ( int i = 0 ; i < k; i++) for ( int j = 0 ; j < 26 ; j++) freq[i][j] = 0 ; for ( int i = 0 ; i < n; i++) { // Increase the frequency // of each character freq[i % k][s.charAt(i) - 'a' ] += 1 ; } int ans = 0 ; // Total number of periods // of size K in the String int totalpositions = n / k; for ( int i = 0 ; i < k; i++) { int maxfrequency = 0 ; for ( int j = 0 ; j < 26 ; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency && allowed[j] == true ) maxfrequency = freq[i][j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0 )); } System.out.print(ans + "\n" ); } // Driver code public static void main(String[] args) { String S = "nihsiakyt" ; int n = S.length(); int K = 3 ; char []A = { 'n' , 'i' , 'p' , 's' , 'q' }; int p = A.length; minFlip(S, n, K, A, p); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 code to find the minimum # number of swaps required to # make the string K periodic def minFlip(s, n, k, a, p): allowed = [ 0 ] * 26 for i in range (p): # Mark all allowed # characters as true allowed[ ord (a[i]) - ord ( 'a' )] = True freq = [[ 0 for x in range ( 26 )] for y in range (k)] # Initialize the freq array to 0 for i in range (k): for j in range ( 26 ): freq[i][j] = 0 for i in range (n): # Increase the frequency # of each character freq[i % k][ ord (s[i]) - ord ( 'a' )] + = 1 ans = 0 # Total number of periods of # size K in the string totalpositions = n / / k for i in range (k): maxfrequency = 0 for j in range ( 26 ): # Check if the current character # is present in allowed # and whether the current # frequency is greater than # all previous frequencies # for this position if (freq[i][j] > maxfrequency and allowed[j] = = True ): maxfrequency = freq[i][j] # Update the answer by # subtracting the maxfrequency # from total positions # if there exist extra character # at the end of the string # apart from the n/k characters # then add 1. ans + = (totalpositions - maxfrequency) if (i % k < n % k): ans + = 1 print (ans) # Driver code if __name__ = = "__main__" : S = "nihsiakyt" n = len (S) K = 3 A = [ 'n' , 'i' , 'p' , 's' , 'q' ] p = len (A) minFlip(S, n, K, A, p) # This code is contributed by chitranayal |
C#
// C# code to find the minimum // number of swaps required to // make the String K periodic using System; class GFG{ static void minFlip(String s, int n, int k, char []a, int p) { bool []allowed = new bool [26]; for ( int i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a' ] = true ; } char [,]freq = new char [k, 26]; // Initialize the freq array to 0 for ( int i = 0; i < k; i++) for ( int j = 0; j < 26; j++) freq[i, j] = ( char )0; for ( int i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k, s[i] - 'a' ] += ( char )1; } int ans = 0; // Total number of periods // of size K in the String int totalpositions = n / k; for ( int i = 0; i < k; i++) { int maxfrequency = 0; for ( int j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i, j] > maxfrequency && allowed[j] == true ) maxfrequency = freq[i, j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } Console.Write(ans + "\n" ); } // Driver code public static void Main(String[] args) { String S = "nihsiakyt" ; int n = S.Length; int K = 3; char []A = { 'n' , 'i' , 'p' , 's' , 'q' }; int p = A.Length; minFlip(S, n, K, A, p); } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // Javascript code for // the above approach. function minFlip(s, n, k, a, p) { let allowed = Array.from({length: 26}, (_, i) => 0); for (let i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i].charCodeAt() - 'a' .charCodeAt()] = true ; } let freq = new Array(k); for ( var i = 0; i < freq.length; i++) { freq[i] = new Array(2); } // Initialize the freq array to 0 for (let i = 0; i < k; i++) for (let j = 0; j < 26; j++) freq[i][j] = 0; for (let i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k][s[i].charCodeAt() - 'a' .charCodeAt()] += 1; } let ans = 0; // Total number of periods // of size K in the String let totalpositions = Math.floor(n / k); for (let i = 0; i < k; i++) { let maxfrequency = 0; for (let j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency && allowed[j] == true ) maxfrequency = freq[i][j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } document.write(ans + "\n" ); } // Driver code let S = "nihsiakyt" ; let n = S.length; let K = 3; let A = [ 'n' , 'i' , 'p' , 's' , 'q' ]; let p = A.length; minFlip(S, n, K, A, p); </script> |
Output:
6
Time Complexity: O(max(p, 26*k, n)), where p is the size of the given array, n is the length of the given string and k is a given integer.
Auxiliary Space: O(k * 26)
Contact Us