Queries to find first occurrence of a character in a given range | C ++ implementation for the above approach ; Function to find the first occurence for a given range ; N = length of string ; M = length of queries ; Stores the indices of a character ; Traverse the string ; Push the index i into the vector [ s [ i ] ] ; Traverse the query ; Stores the value L ; Stores the value R ; Stores the character C ; Find index >= L in the vector v ; If there is no index of C >= L ; Stores the value at idx ; If idx > R ; Otherwise ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int firstOccurence ( string s , vector < pair < pair < int , int > , char > > Q ) { int N = s . size ( ) ; int M = Q . size ( ) ; map < char , vector < int > > v ; for ( int i = 0 ; i < N ; i ++ ) { v [ s [ i ] ] . push_back ( i ) ; } for ( int i = 0 ; i < M ; i ++ ) { int left = Q [ i ] . first . first ; int right = Q [ i ] . first . second ; char c = Q [ i ] . second ; if ( v . size ( ) == 0 ) { cout << " - 1 ▁ " ; continue ; } int idx = lower_bound ( v . begin ( ) , v . end ( ) , left ) - v . begin ( ) ; if ( idx == ( int ) v . size ( ) ) { cout << " - 1 ▁ " ; continue ; } idx = v [ idx ] ; if ( idx > right ) { cout << " - 1 ▁ " ; } else { cout << idx << " ▁ " ; } } } int main ( ) { string S = " abcabcabc " ; vector < pair < pair < int , int > , char > > Q = { { { 0 , 3 } , ' a ' } , { { 0 , 2 } , ' b ' } , { { 2 , 4 } , ' z ' } } ; firstOccurence ( S , Q ) ; return 0 ; }