Minimize Cost to sort a String in Increasing Order of Frequencies of Characters | C ++ program to implement above approach ; For a single character ; Stores count of repetitions of a character ; If repeating character ; Otherwise ; Store frequency ; Reset count ; Insert the last character block ; Sort the frequencies ; Stores the minimum cost of all operations ; Store the absolute difference of i - th frequencies of ordered and unordered sequences ; Return the minimum cost ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sortString ( string S ) { vector < int > sorted , original ; bool insert = false ; if ( S . length ( ) == 1 ) { cout << 0 << endl ; } int curr = 1 ; for ( int i = 0 ; i < ( S . length ( ) - 1 ) ; i ++ ) { if ( S [ i ] == S [ i + 1 ] ) { curr += 1 ; insert = false ; } else { sorted . push_back ( curr ) ; original . push_back ( curr ) ; curr = 1 ; insert = true ; } } if ( ( S [ ( S . length ( ) - 1 ) ] != S [ ( S . length ( ) - 2 ) ] ) insert == false ) { sorted . push_back ( curr ) ; original . push_back ( curr ) ; } sort ( sorted . begin ( ) , sorted . end ( ) ) ; int t_cost = 0 ; for ( int i = 0 ; i < sorted . size ( ) ; i ++ ) { t_cost += abs ( sorted [ i ] - original [ i ] ) ; } return ( t_cost / 2 ) ; } int main ( ) { string S = " aabbcccdeffffggghhhhhii " ; cout << sortString ( S ) ; return 0 ; }