Sum of indices of Characters removed to obtain an Empty String based on given conditions | C ++ Program to implement the above approach ; Function to add index of the deleted character ; If index is beyond the range ; Insert the index of the deleted characeter ; Search over the subtrees to find the desired index ; Function to return count of deleted indices which are to the left of the current index ; Function to generate the sum of indices ; Stores the original index of the characters in sorted order of key ; Traverse the map ; Extract smallest index of smallest character ; Delete the character from the map if it has no remaining occurrence ; Stores the original index ; Count of elements removed to the left of current character ; Current index of the current character ; For 1 - based indexing ; Insert the deleted index in the segment tree ; Final answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void add_seg ( int seg [ ] , int start , int end , int current , int index ) { if ( index > end or index < start ) return ; if ( start == end ) { seg [ current ] = 1 ; return ; } int mid = ( start + end ) / 2 ; add_seg ( seg , start , mid , 2 * current + 1 , index ) ; add_seg ( seg , mid + 1 , end , 2 * current + 2 , index ) ; seg [ current ] = seg [ 2 * current + 1 ] + seg [ 2 * current + 2 ] ; } int deleted ( int seg [ ] , int l , int r , int start , int end , int current ) { if ( end < l or start > r ) return 0 ; if ( start >= l and end <= r ) return seg [ current ] ; int mid = ( start + end ) / 2 ; return deleted ( seg , l , r , start , mid , 2 * current + 1 ) + deleted ( seg , l , r , mid + 1 , end , 2 * current + 2 ) ; } void sumOfIndices ( string s ) { int N = s . size ( ) ; int x = int ( ceil ( log2 ( N ) ) ) ; int seg_size = 2 * ( int ) pow ( 2 , x ) - 1 ; int segment [ seg_size ] = { 0 } ; int count = 0 ; map < int , queue < int > > fre ; for ( int i = 0 ; i < N ; i ++ ) { fre [ s [ i ] ] . push ( i ) ; } while ( fre . empty ( ) == false ) { auto it = fre . begin ( ) ; if ( it -> second . empty ( ) == true ) fre . erase ( it -> first ) ; else { int original_index = it -> second . front ( ) ; int curr_index = deleted ( segment , 0 , original_index - 1 , 0 , N - 1 , 0 ) ; int new_index = original_index - curr_index ; count += new_index + 1 ; add_seg ( segment , 0 , N - 1 , 0 , original_index ) ; it -> second . pop ( ) ; } } cout << count << endl ; } int main ( ) { string s = " geeksforgeeks " ; sumOfIndices ( s ) ; }