Sum of indices of Characters removed to obtain an Empty String based on given conditions | Python3 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 math , collections NEW_LINE def add_seg ( seg , start , end , current , index ) : NEW_LINE INDENT if ( index > end or index < start ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( start == end ) : NEW_LINE INDENT seg [ current ] = 1 NEW_LINE return NEW_LINE DEDENT mid = int ( ( start + end ) / 2 ) NEW_LINE add_seg ( seg , start , mid , 2 * current + 1 , index ) NEW_LINE add_seg ( seg , mid + 1 , end , 2 * current + 2 , index ) NEW_LINE seg [ current ] = seg [ 2 * current + 1 ] + seg [ 2 * current + 2 ] NEW_LINE DEDENT def deleted ( seg , l , r , start , end , current ) : NEW_LINE INDENT if ( end < l or start > r ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( start >= l and end <= r ) : NEW_LINE INDENT return seg [ current ] NEW_LINE DEDENT mid = int ( ( start + end ) / 2 ) NEW_LINE return deleted ( seg , l , r , start , mid , 2 * current + 1 ) + deleted ( seg , l , r , mid + 1 , end , 2 * current + 2 ) NEW_LINE DEDENT def sumOfIndices ( s ) : NEW_LINE INDENT N = len ( s ) NEW_LINE x = ( int ) ( math . ceil ( math . log ( N ) / math . log ( 2 ) ) ) NEW_LINE seg_size = 2 * pow ( 2 , x ) - 1 NEW_LINE segment = [ 0 ] * ( seg_size ) NEW_LINE count = 4 NEW_LINE fre = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT key = ( ord ) ( s [ i ] ) NEW_LINE if key in fre : NEW_LINE INDENT que = fre [ key ] NEW_LINE DEDENT else : NEW_LINE INDENT que = collections . deque ( [ ] ) NEW_LINE DEDENT que . append ( i ) NEW_LINE fre [ key ] = que NEW_LINE DEDENT while len ( fre ) > 0 : NEW_LINE INDENT it = list ( fre . keys ( ) ) [ 0 ] NEW_LINE if len ( fre [ it ] ) == 0 : NEW_LINE INDENT del fre [ it ] NEW_LINE DEDENT else : NEW_LINE INDENT que = fre [ it ] NEW_LINE original_index = que [ 0 ] NEW_LINE curr_index = deleted ( segment , 0 , original_index - 1 , 0 , N - 1 , 0 ) NEW_LINE new_index = original_index - curr_index NEW_LINE count += new_index + 1 NEW_LINE add_seg ( segment , 0 , N - 1 , 0 , original_index ) NEW_LINE que . popleft ( ) NEW_LINE fre [ it ] = que NEW_LINE DEDENT DEDENT print ( count ) NEW_LINE DEDENT s = " geeksforgeeks " NEW_LINE sumOfIndices ( s ) NEW_LINE