Sum of indices of Characters removed to obtain an Empty String based on given conditions | Java 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void add_seg ( int seg [ ] , int start , int end , int current , int index ) { if ( index > end 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 ] ; } static int deleted ( int seg [ ] , int l , int r , int start , int end , int current ) { if ( end < l start > r ) return 0 ; if ( start >= l && 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 ) ; } static void sumOfIndices ( String s ) { int N = s . length ( ) ; int x = ( int ) ( Math . ceil ( Math . log ( N ) / Math . log ( 2 ) ) ) ; int seg_size = 2 * ( int ) Math . pow ( 2 , x ) - 1 ; int segment [ ] = new int [ seg_size ] ; int count = 0 ; TreeMap < Integer , ArrayDeque < Integer > > fre = new TreeMap < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { int key = ( int ) ( s . charAt ( i ) ) ; ArrayDeque < Integer > que = fre . getOrDefault ( key , new ArrayDeque < > ( ) ) ; que . addLast ( i ) ; fre . put ( key , que ) ; } while ( ! fre . isEmpty ( ) ) { int it = fre . firstKey ( ) ; if ( fre . get ( it ) . size ( ) == 0 ) fre . remove ( it ) ; else { ArrayDeque < Integer > que = fre . get ( it ) ; int original_index = que . getFirst ( ) ; 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 ) ; que . removeFirst ( ) ; fre . put ( it , que ) ; } } System . out . println ( count ) ; } public static void main ( String [ ] args ) { String s = " geeksforgeeks " ; sumOfIndices ( s ) ; } }