Minimum replacements required to obtain a K | Java 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
import java . util . * ; class GFG { static int findMinimumChanges ( int N , int K , char [ ] S ) { int ans = 0 ; for ( int i = 0 ; i < ( K + 1 ) / 2 ; i ++ ) { HashMap < Character , Integer > mp = new HashMap < > ( ) ; for ( int j = i ; j < N ; j += K ) { if ( mp . containsKey ( S [ j ] ) ) { mp . put ( S [ j ] , mp . get ( S [ j ] ) + 1 ) ; } else { mp . put ( S [ j ] , 1 ) ; } } for ( int j = N - i - 1 ; j >= 0 ; j -= K ) { if ( K % 2 == 1 && i == K / 2 ) break ; if ( mp . containsKey ( S [ j ] ) ) { mp . put ( S [ j ] , mp . get ( S [ j ] ) + 1 ) ; } else { mp . put ( S [ j ] , 1 ) ; } } int curr_max = Integer . MIN_VALUE ; for ( Map . Entry < Character , Integer > p : mp . entrySet ( ) ) { curr_max = Math . max ( curr_max , p . getValue ( ) ) ; } if ( ( K % 2 == 1 ) && i == K / 2 ) ans += ( N / K - curr_max ) ; else ans += ( N / K * 2 - curr_max ) ; } return ans ; } public static void main ( String [ ] args ) { String S = " aabbcbbcb " ; int N = S . length ( ) ; int K = 3 ; System . out . print ( findMinimumChanges ( N , K , S . toCharArray ( ) ) ) ; } }