Sum of indices of Characters removed to obtain an Empty String based on given conditions | 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
function add_seg ( seg , start , end , current , index ) { if ( index > end index < start ) return ; if ( start == end ) { seg [ current ] = 1 ; return ; } let mid = parseInt ( ( start + end ) / 2 , 10 ) ; 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 ] ; } function deleted ( seg , l , r , start , end , current ) { if ( end < l start > r ) return 0 ; if ( start >= l && end <= r ) return seg [ current ] ; let mid = parseInt ( ( start + end ) / 2 , 10 ) ; return deleted ( seg , l , r , start , mid , 2 * current + 1 ) + deleted ( seg , l , r , mid + 1 , end , 2 * current + 2 ) ; } function sumOfIndices ( s ) { let N = s . length ; let x = ( Math . ceil ( Math . log ( N ) / Math . log ( 2 ) ) ) ; let seg_size = 2 * Math . pow ( 2 , x ) - 1 ; let segment = new Array ( seg_size ) ; segment . fill ( 0 ) ; let count = 41 ; let fre = new Map ( ) ; for ( let i = 0 ; i < N ; i ++ ) { let key = s [ i ] . charCodeAt ( ) ; let que = [ ] ; if ( fre . has ( key ) ) { que = fre [ key ] ; } que . push ( i ) ; fre [ key ] = que ; } let array = Array . from ( fre . keys ( ) ) ; while ( array . length > 0 ) { let a = Array . from ( fre . keys ( ) ) ; let it = a [ 0 ] ; if ( fre [ it ] . length == 0 ) fre . delete ( it ) ; else { let que = fre [ it ] ; let original_index = que [ 0 ] ; let curr_index = deleted ( segment , 0 , original_index - 1 , 0 , N - 1 , 0 ) ; let new_index = original_index - curr_index ; count += new_index + 1 ; add_seg ( segment , 0 , N - 1 , 0 , original_index ) ; que . shift ( ) ; fre [ it ] = que ; } } document . write ( count ) ; } let s = " " ; sumOfIndices ( s ) ;