Minimum cost to modify a string | C ++ implementation of the approach ; Function to return the minimum cost ; Initialize result ; To store the frequency of characters of the string ; Initialize array with 0 ; Update the frequencies of the characters of the string ; Loop to check all windows from a - z where window size is K ; Starting index of window ; Ending index of window ; Check if the string contains character ; Check if the character is on left side of window find the cost of modification for character add value to count calculate nearest distance of modification ; Check if the character is on right side of window find the cost of modification for character add value to count calculate nearest distance of modification ; Find the minimum of all costs for modifying the string ; Loop to check all windows Here window contains characters before z and after z of window size K ; Starting index of window ; Ending index of window ; Check if the string contains character ; If characters are outside window find the cost for modifying character add value to count ; Find the minimum of all costs for modifying the string ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCost ( string str , int K ) { int n = str . length ( ) ; int res = 999999999 , count = 0 , a , b ; int cnt [ 27 ] ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int i = 0 ; i < n ; i ++ ) cnt [ str [ i ] - ' a ' + 1 ] ++ ; for ( int i = 1 ; i < ( 26 - K + 1 ) ; i ++ ) { a = i ; b = i + K ; count = 0 ; for ( int j = 1 ; j <= 26 ; j ++ ) { if ( cnt [ j ] > 0 ) { if ( j >= a && j >= b ) count = count + ( min ( j - b , 25 - j + a + 1 ) ) * cnt [ j ] ; else if ( j <= a && j <= b ) count = count + ( min ( a - j , 25 + j - b + 1 ) ) * cnt [ j ] ; } } res = min ( res , count ) ; } for ( int i = 26 - K + 1 ; i <= 26 ; i ++ ) { a = i ; b = ( i + K ) % 26 ; count = 0 ; for ( int j = 1 ; j <= 26 ; j ++ ) { if ( cnt [ j ] > 0 ) { if ( j >= b and j <= a ) count = count + ( min ( j - b , a - j ) ) * cnt [ j ] ; } } res = min ( res , count ) ; } return res ; } int main ( ) { string str = " abcdefghi " ; int K = 2 ; cout << minCost ( str , K ) ; return 0 ; }