Minimize cost to empty a given string by removing characters alphabetically | C ++ program for the above approach ; Function to find the minimum cost required to remove each character of the string in alphabetical order ; Stores the frequency of characters of the string ; Iterate through the string ; Count the number of characters smaller than the present character ; If no smaller character precedes current character ; Increase the frequency of the current character ; Return the total cost ; Driver Code ; Given string str ; Function call
#include <bits/stdc++.h> NEW_LINE #include <vector> NEW_LINE using namespace std ; int minSteps ( string str , int N ) { int smaller , cost = 0 ; int f [ 26 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { int curr_ele = str [ i ] - ' a ' ; smaller = 0 ; for ( int j = 0 ; j <= curr_ele ; j ++ ) { if ( f [ j ] ) smaller += f [ j ] ; } if ( smaller == 0 ) cost += ( i + 1 ) ; else cost += ( i - smaller + 1 ) ; f [ str [ i ] - ' a ' ] ++ ; } return cost ; } int main ( ) { string str = " abcab " ; int N = str . size ( ) ; cout << minSteps ( str , N ) ; return 0 ; }