Minimum number of swaps required to make the string K periodic | C ++ code to find the minimum number of swaps required to make the string K periodic ; Mark all allowed characters as true ; Initialize the freq array to 0 ; Increase the frequency of each character ; Total number of periods of size K in the string ; Check if the current character is present in allowed and whether the current frequency is greater than all previous frequencies for this position ; 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. ; Driver code
#include <bits/stdc++.h> NEW_LINE 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 ++ ) { allowed [ a [ i ] - ' a ' ] = true ; } char freq [ k ] [ 26 ] ; 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 ++ ) { freq [ i % k ] [ s [ i ] - ' a ' ] += 1 ; } int ans = 0 ; int totalpositions = n / k ; for ( int i = 0 ; i < k ; i ++ ) { int maxfrequency = 0 ; for ( int j = 0 ; j < 26 ; j ++ ) { if ( freq [ i ] [ j ] > maxfrequency and allowed [ j ] == true ) maxfrequency = freq [ i ] [ j ] ; } ans += ( totalpositions - maxfrequency + ( ( i % k < n % k ) ? 1 : 0 ) ) ; } cout << ans << endl ; } 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 ; }