# 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 Ă— 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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:S= “abcabcabc”, Q[][] = { { 0, 3, ‘a’ }, { 0, 2, ‘b’ }, { 2, 4, ‘z’ } }Output:0 1 -1Explanation:

- 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 as the character ‘z’ does not occur in the range [2, 4].

Input:S= “geeksforgeeks”, Q[][] = { { 0, 12, ‘f’ }, { 0, 2, ‘g’ }, { 6, 12, ‘f’ } }Output:5 0 -1Explanation:

- 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 ‘g’ in the range [0, 2].- Third query: Print -1 as 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**. **Time Complexity:** O(M * Q)**Auxiliary Space: **O(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 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**.

- If the size of

Below is the implementation of the above approach:

## C++

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

## Python3

`# Python3 implementation` `# for the above approach` `from` `bisect ` `import` `bisect_left` `# Function to find the first occurence` `# for a given range` `def` `firstOccurence(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 Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `S ` `=` `"abcabcabc"` `;` ` ` `Q ` `=` `[ [ ` `0` `, ` `3` `, ` `'a'` `],[ ` `0` `, ` `2` `, ` `'b'` `],[ ` `2` `, ` `4` `, ` `'z'` `]]` ` ` `firstOccurence(S, Q)` ` ` `# This code is contributed by mohit kumar 29.` |

**Output:**

0 1 -1

**Time Complexity:** O(M * log(N))**Auxiliary Space: **O(N)