text: Minimum replacements required to obtain a K | C ++ program for the above approach ; Function to find the minimum number of changes to make the string K - periodic and palindrome ; Initialize ans with 0 ; Iterate from 0 to ( K + 1 ) / 2 ; Store frequency of character ; Iterate through all indices , i , i + K , i + 2 k ... . and store the frequency of character ; Increase the frequency of current character ; Iterate through all indices K - i , 2 K - i , 3 K - i ... . and store the frequency of character ; If K is odd & i is samw as K / 2 , break the loop ; Increase the frequency of current character ; Find the maximum frequency of a character among all visited characters ; If K is odd and i is same as K / 2 then , only N / K characters is visited ; Otherwise N / K * 2 characters has visited ; Return the result ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinimumChanges ( int N , int K , string S ) { int ans = 0 ; for ( int i = 0 ; i < ( K + 1 ) / 2 ; i ++ ) { map < char , int > mp ; for ( int j = i ; j < N ; j += K ) { mp [ S [ j ] ] ++ ; } for ( int j = N - i - 1 ; j >= 0 ; j -= K ) { if ( K & 1 and i == K / 2 ) break ; mp [ S [ j ] ] ++ ; } int curr_max = INT_MIN ; for ( auto p : mp ) curr_max = max ( curr_max , p . second ) ; if ( K & 1 and i == K / 2 ) ans += ( N / K - curr_max ) ; else ans += ( N / K * 2 - curr_max ) ; } return ans ; } int main ( ) { string S = " aabbcbbcb " ; int N = S . length ( ) ; int K = 3 ; cout << findMinimumChanges ( N , K , S ) ; return 0 ; }