Minimize Cost to sort a String in Increasing Order of Frequencies of Characters | Java 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
import java . util . * ; class GFG { public static int sortString ( String S ) { Vector < Integer > sorted = new Vector < Integer > ( ) ; Vector < Integer > original = new Vector < Integer > ( ) ; boolean insert = false ; if ( S . length ( ) == 1 ) { System . out . println ( 0 ) ; } int curr = 1 ; for ( int i = 0 ; i < ( S . length ( ) - 1 ) ; i ++ ) { if ( S . charAt ( i ) == S . charAt ( i + 1 ) ) { curr += 1 ; insert = false ; } else { sorted . add ( curr ) ; original . add ( curr ) ; curr = 1 ; insert = true ; } } if ( ( S . charAt ( S . length ( ) - 1 ) != S . charAt ( S . length ( ) - 2 ) ) insert == false ) { sorted . add ( curr ) ; original . add ( curr ) ; } Collections . sort ( sorted ) ; int t_cost = 0 ; for ( int i = 0 ; i < sorted . size ( ) ; i ++ ) { t_cost += Math . abs ( sorted . get ( i ) - original . get ( i ) ) ; } return ( t_cost / 2 ) ; } public static void main ( String [ ] args ) { String S = " aabbcccdeffffggghhhhhii " ; System . out . print ( sortString ( S ) ) ; } }