Queries to find total number of duplicate character in range L to R in the string S | Python implementation to Find the total number of duplicate character in a range L to R for Q number of queries in a string S ; Vector of vector to store position of all characters as they appear in string ; Function to store position of each character ; Inserting position of each character as they appear ; Function to calculate duplicate characters for Q queries ; Variable to count duplicates ; Iterate over all 26 characters ; Finding the first element which is less than or equal to L ; Check if first pointer exists and is less than R ; Incrementing first pointer to check if the next duplicate element exists ; Check if the next element exists and is less than R ; Driver Code
import bisect NEW_LINE v = [ [ ] for _ in range ( 26 ) ] NEW_LINE def calculate ( s : str ) -> None : NEW_LINE INDENT for i in range ( len ( s ) ) : NEW_LINE INDENT v [ ord ( s [ i ] ) - ord ( ' a ' ) ] . append ( i ) NEW_LINE DEDENT DEDENT def query ( L : int , R : int ) -> None : NEW_LINE INDENT duplicates = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT first = bisect . bisect_left ( v [ i ] , L - 1 ) NEW_LINE if ( first < len ( v [ i ] ) and v [ i ] [ first ] < R ) : NEW_LINE INDENT first += 1 NEW_LINE if ( first < len ( v [ i ] ) and v [ i ] [ first ] < R ) : NEW_LINE INDENT duplicates += 1 NEW_LINE DEDENT DEDENT DEDENT print ( duplicates ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " geeksforgeeks " NEW_LINE Q = 2 NEW_LINE l1 = 1 NEW_LINE r1 = 5 NEW_LINE l2 = 4 NEW_LINE r2 = 8 NEW_LINE calculate ( s ) NEW_LINE query ( l1 , r1 ) NEW_LINE query ( l2 , r2 ) NEW_LINE DEDENT