Minimum characters to be replaced to make a string concatenation of a K | Java program for the above approach ; Function to add an edge to graph ; Function to perform DFS traversal on the graph recursively from a given vertex u ; Visit the current vertex ; Total number of nodes in this component ; Increment the frequency of u ; Function for finding the minimum number changes required in given String ; Form the edges according to the given conditions ; Find minimum number of operations ; Frequency array for finding the most frequent character ; Frequency array for finding the most frequent character ; Finding most frequent character ; Change rest of the characters to most frequent one ; Print total number of changes ; Driver Code ; Function Call
import java . util . * ; class GFG { static void addEdge ( Vector < Integer > adj [ ] , int u , int v ) { adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } static int cnt = 0 ; static boolean [ ] visited ; static void DFS ( int u , Vector < Integer > adj [ ] , int fre [ ] , String S ) { visited [ u ] = true ; cnt ++ ; fre [ S . charAt ( u ) - ' a ' ] ++ ; for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( ! visited [ adj [ u ] . get ( i ) ] ) { DFS ( adj [ u ] . get ( i ) , adj , fre , S ) ; } } } static void minimumOperations ( String S , int m ) { int V = 100 ; @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] adj = new Vector [ V ] ; int total = 0 , N = S . length ( ) ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { addEdge ( adj , i , N - i - 1 ) ; addEdge ( adj , N - i - 1 , i ) ; } for ( int i = 0 ; i < N - m ; i ++ ) { addEdge ( adj , i , i + m ) ; addEdge ( adj , i + m , i ) ; } visited = new boolean [ V ] ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { int fre [ ] = new int [ 26 ] ; cnt = 0 ; int maxx = - 1 ; DFS ( i , adj , fre , S ) ; for ( int j = 0 ; j < 26 ; j ++ ) maxx = Math . max ( maxx , fre [ j ] ) ; total += cnt - maxx ; } } System . out . print ( total ) ; } public static void main ( String [ ] args ) { String S = " abaaba " ; int K = 2 ; minimumOperations ( S , K ) ; } }