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
using System ; using System . Collections . Generic ; class GFG { public static int sortString ( string S ) { List < int > sorted = new List < int > ( ) ; List < int > original = new List < int > ( ) ; bool insert = false ; if ( S . Length == 1 ) { Console . WriteLine ( 0 ) ; } int curr = 1 ; for ( int i = 0 ; i < ( S . Length - 1 ) ; i ++ ) { if ( S [ i ] == S [ i + 1 ] ) { curr += 1 ; insert = false ; } else { sorted . Add ( curr ) ; original . Add ( curr ) ; curr = 1 ; insert = true ; } } if ( ( S [ S . Length - 1 ] != S [ S . Length - 2 ] ) insert == false ) { sorted . Add ( curr ) ; original . Add ( curr ) ; } sorted . Sort ( ) ; int t_cost = 0 ; for ( int i = 0 ; i < sorted . Count ; i ++ ) { t_cost += Math . Abs ( sorted [ i ] - original [ i ] ) ; } return ( t_cost / 2 ) ; } static void Main ( ) { string S = " aabbcccdeffffggghhhhhii " ; Console . Write ( sortString ( S ) ) ; } }