Queries to find first occurrence of a character in a given range
Given a string S of length N and an array Q[][] of dimension M X 3 consisting of queries of type {L, R, C}, the task is to print the first index of the character C in the range [L, R], if found. Otherwise, print -1.Examples:
Input: S= “abcabcabc”, Q[][] = { { 0, 3, ‘a’ }, { 0, 2, ‘b’ }, { 2, 4, ‘z’ } }
Output: 0 1 -1
Explanation:
- First query: Print 0 which is the first index of character ‘a’ in the range [0, 3].
- Second query: Print 1, which is the first index of character ‘b’ in the range [0, 2].
- Third query: Print -1 when the character ‘z’ does not occur in the range [2, 4].
Input: S= “CodesforCodes”, Q[][] = { { 0, 12, ‘f’ }, { 0, 2, ‘C’ }, { 6, 12, ‘f’ } }
Output: 5 0 -1
Explanation:
- First query: Print 5, which is the first index of character ‘f’ in the range [0, 12].
- Second query: Print 0 which is the first index of character ‘C’ in the range [0, 2].
- Third query: Print -1 when the character ‘f’ does not occur in the range [6, 12].
Naive Approach: The simplest approach is to traverse the string over the range of indices [L, R] for each query and print the first occurrence of character C if found. Otherwise, print -1.
Efficient Approach: The above approach can be optimized by pre-storing the indices of characters in the map of vectors and using binary search to find the index in the range [L, R] in the vector of characters C. Follow the steps below to solve the problem:
- Initialize a Map < char, vector < int > >, say V, to store indices of all occurrences of a character.
- Traverse the string and update V.
- Traverse the an array Q:
- If the size of V[C] is zero then print -1.
- Otherwise, find the index by using binary search in vector V[C] i.e lower_bound(V[C].begin(), V[C].end(), L) – V[C].begin() and store it in a variable, say idx.
- If idx = N or idx > R, then print -1.
- Otherwise, print the index idx.
Below is the implementation of the above approach:
Python3
# Python3 implementation# for the above approachfrom bisect import bisect_left# Function to find the first occurrence# for a given rangedef firstOccurrence(s, Q): # N = length of string N = len(s) # M = length of queries M = len(Q) # Stores the indices of a character v = [[] for i in range(26)] # Traverse the string for i in range(N): # Push the index i # into the vector[s[i]] v[ord(s[i]) - ord('a')].append(i) # Traverse the query for i in range(M): # Stores the value L left = Q[i][0] # Stores the value R right = Q[i][1] # Stores the character C c = Q[i][2] if (len(v[ord(c) - ord('a')]) == 0): print ("-1") continue # Find index >= L in # the vector v idx = bisect_left(v[ord(c) - ord('a')], left) # If there is no index of C >= L if (idx == len(v[ord(c) - ord('a')])): print("-1 ") continue # Stores the value at idx idx = v[ord(c) - ord('a')][idx] # If idx > R if (idx > right): print ("-1 ") # Otherwise else: print(idx, end=" ")# Driver Codeif __name__ == '__main__': S = "abcabcabc"; Q = [ [ 0, 3 , 'a'],[ 0, 2 , 'b' ],[ 2, 4, 'z']] firstOccurrence(S, Q) |
Output:
0 1 -1