Queries to find total number of duplicate character in range L to R in the string S | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > v ( 26 ) ; void calculate ( string s ) { for ( int i = 0 ; i < s . size ( ) ; i ++ ) { v [ s [ i ] - ' a ' ] . push_back ( i ) ; } } void query ( int L , int R ) { int duplicates = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { auto first = lower_bound ( v [ i ] . begin ( ) , v [ i ] . end ( ) , L - 1 ) ; if ( first != v [ i ] . end ( ) && * first < R ) { first ++ ; if ( first != v [ i ] . end ( ) && * first < R ) duplicates ++ ; } } cout << duplicates << endl ; } int main ( ) { string s = " geeksforgeeks " ; int Q = 2 ; int l1 = 1 , r1 = 5 ; int l2 = 4 , r2 = 8 ; calculate ( s ) ; query ( l1 , r1 ) ; query ( l2 , r2 ) ; return 0 ; }