Minimum characters to be replaced to make a string concatenation of a K | C ++ 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
#include " bits / stdc + + . h " NEW_LINE using namespace std ; void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void DFS ( int u , vector < int > adj [ ] , int & cnt , vector < bool > & visited , int fre [ ] , string S ) { visited [ u ] = true ; cnt ++ ; fre [ S [ u ] - ' a ' ] ++ ; for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) { if ( ! visited [ adj [ u ] [ i ] ] ) { DFS ( adj [ u ] [ i ] , adj , cnt , visited , fre , S ) ; } } } int minimumOperations ( string & S , int m ) { int V = 100 ; vector < int > adj [ V ] ; int total = 0 , N = S . length ( ) ; 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 ) ; } vector < bool > visited ( V , 0 ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { int fre [ 26 ] = { 0 } ; int cnt = 0 , maxx = -1 ; DFS ( i , adj , cnt , visited , fre , S ) ; for ( int j = 0 ; j < 26 ; j ++ ) maxx = max ( maxx , fre [ j ] ) ; total += cnt - maxx ; } } cout << total ; } int main ( ) { string S = " abaaba " ; int K = 2 ; minimumOperations ( S , K ) ; return 0 ; }