Queries to find first occurrence of a character in a given range | Python3 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
from bisect import bisect_left NEW_LINE def firstOccurence ( s , Q ) : NEW_LINE INDENT N = len ( s ) NEW_LINE M = len ( Q ) NEW_LINE v = [ [ ] for i in range ( 26 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT v [ ord ( s [ i ] ) - ord ( ' a ' ) ] . append ( i ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT left = Q [ i ] [ 0 ] NEW_LINE right = Q [ i ] [ 1 ] NEW_LINE c = Q [ i ] [ 2 ] NEW_LINE if ( len ( v [ ord ( c ) - ord ( ' a ' ) ] ) == 0 ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE continue NEW_LINE DEDENT idx = bisect_left ( v [ ord ( c ) - ord ( ' a ' ) ] , left ) NEW_LINE if ( idx == len ( v [ ord ( c ) - ord ( ' a ' ) ] ) ) : NEW_LINE INDENT print ( " - 1 ▁ " ) NEW_LINE continue NEW_LINE DEDENT idx = v [ ord ( c ) - ord ( ' a ' ) ] [ idx ] NEW_LINE if ( idx > right ) : NEW_LINE INDENT print ( " - 1 ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( idx , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " abcabcabc " ; NEW_LINE Q = [ [ 0 , 3 , ' a ' ] , [ 0 , 2 , ' b ' ] , [ 2 , 4 , ' z ' ] ] NEW_LINE firstOccurence ( S , Q ) NEW_LINE DEDENT