# Index of character depending on frequency count in string

Given a string **str** containing only lowercase characters, the task is to answer **Q** queries of the following type:

**1 C X:**Find the largest**i**such that**str[0…i]**has exactly**X**occurrence of the character**C**.**2 C X:**Find the smallest**i**such that**str[0…i]**has exactly**X**occurrence of the character**C**.

**Example:**

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:str = “geeksforgeeks”, query[] = {{1, ‘e’, 2}, {2, ‘k’, 2}}Output:

8

11

Query 1: “geeksforg” is the largest substring starting at str[0] with ‘e’ appearing exactly twice and the index of the last character is 8.

Query 2: “geeksforgeek” is the smallest substring starting at str[0] with ‘k’ appearing exactly twice and the index of the last character is 11.Input:str = “abcdabcd”, query[] = {{1, ‘a’, 1}, {2, ‘a’, 2}}Output:

3

4

**Approach:** Create two 2-dimensional arrays **L[][]** and **F[][]** such that **L[i][j]** stores the largest **i** such that the **i ^{th}** character appears exactly

**j**times in

^{th}**str[0…i]**and

**F[i][j]**stores the smallest

**i**such that the

**i**character appears exactly

^{th}**j**times in

^{th}**str[0…i]**. In order to do so, traverse the whole string and maintain a frequency array so that for each iteration/character, its count is updated and then start another loop from

**0**to

**26**(each letter a-z). In the inner loop, if the iterator is equal to character value then update

**L[][]**and

**F[][]**array with the current index position using outer loop iterator otherwise just increment the

**L[][]**array value for other characters by

**1**as only index has been incremented and the character has not occurred. Now, type 1 query can be answered as

**L[given character][Frequency count]**and type 2 query as

**F[given character][Frequency count]**.

Below is the implementation of the above approach.

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `MAX = 26;` `// Function to perform the queries` `void` `performQueries(string str, ` `int` `q, ` `int` `type[],` ` ` `char` `ch[], ` `int` `freq[])` `{` ` ` `int` `n = str.length();` ` ` `// L[i][j] stores the largest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `L[MAX][n];` ` ` `// F[i][j] stores the smallest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `F[MAX][n];` ` ` `// To store the frequency of each` ` ` `// of the character of str` ` ` `int` `cnt[MAX] = { 0 };` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// Current character of str` ` ` `int` `k = str[i] - ` `'a'` `;` ` ` `// Update its frequency` ` ` `cnt[k]++;` ` ` `// For every lowercase character` ` ` `// of the English alphabet` ` ` `for` `(` `int` `j = 0; j < MAX; j++) {` ` ` `// If it is equal to the character` ` ` `// under consideration then update` ` ` `// L[][] and R[][] as it is cnt[j]th` ` ` `// occurrence of character k` ` ` `if` `(k == j) {` ` ` `L[j][cnt[j]] = i;` ` ` `F[j][cnt[j]] = i;` ` ` `}` ` ` `// Only update L[][] as k has not` ` ` `// been occurred so only index` ` ` `// has to be incremented` ` ` `else` ` ` `L[j][cnt[j]] = L[j][cnt[j]] + 1;` ` ` `}` ` ` `}` ` ` `// Perform the queries` ` ` `for` `(` `int` `i = 0; i < q; i++) {` ` ` `// Type 1 query` ` ` `if` `(type[i] == 1) {` ` ` `cout << L[ch[i] - ` `'a'` `][freq[i]];` ` ` `}` ` ` `// Type 2 query` ` ` `else` `{` ` ` `cout << F[ch[i] - ` `'a'` `][freq[i]];` ` ` `}` ` ` `cout << ` `"\n"` `;` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `string str = ` `"geeksforgeeks"` `;` ` ` `// Queries` ` ` `int` `type[] = { 1, 2 };` ` ` `char` `ch[] = { ` `'e'` `, ` `'k'` `};` ` ` `int` `freq[] = { 2, 2 };` ` ` `int` `q = ` `sizeof` `(type) / ` `sizeof` `(` `int` `);` ` ` `// Perform the queries` ` ` `performQueries(str, q, type, ch, freq);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` `static` `int` `MAX = ` `26` `;` `// Function to perform the queries` `static` `void` `performQueries(String str, ` `int` `q, ` `int` `type[],` ` ` `char` `ch[], ` `int` `freq[])` `{` ` ` `int` `n = str.length();` ` ` `// L[i][j] stores the largest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `[][]L = ` `new` `int` `[MAX][n];` ` ` `// F[i][j] stores the smallest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `[][]F = ` `new` `int` `[MAX][n];` ` ` `// To store the frequency of each` ` ` `// of the character of str` ` ` `int` `[]cnt = ` `new` `int` `[MAX];` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `{` ` ` `// Current character of str` ` ` `int` `k = str.charAt(i) - ` `'a'` `;` ` ` `// Update its frequency` ` ` `cnt[k]++;` ` ` `// For every lowercase character` ` ` `// of the English alphabet` ` ` `for` `(` `int` `j = ` `0` `; j < MAX; j++)` ` ` `{` ` ` `// If it is equal to the character` ` ` `// under consideration then update` ` ` `// L[][] and R[][] as it is cnt[j]th` ` ` `// occurrence of character k` ` ` `if` `(k == j)` ` ` `{` ` ` `L[j][cnt[j]] = i;` ` ` `F[j][cnt[j]] = i;` ` ` `}` ` ` `// Only update L[][] as k has not` ` ` `// been occurred so only index` ` ` `// has to be incremented` ` ` `else` ` ` `L[j][cnt[j]] = L[j][cnt[j]] + ` `1` `;` ` ` `}` ` ` `}` ` ` `// Perform the queries` ` ` `for` `(` `int` `i = ` `0` `; i < q; i++)` ` ` `{` ` ` `// Type 1 query` ` ` `if` `(type[i] == ` `1` `)` ` ` `{` ` ` `System.out.print(L[ch[i] - ` `'a'` `][freq[i]]);` ` ` `}` ` ` `// Type 2 query` ` ` `else` ` ` `{` ` ` `System.out.print(F[ch[i] - ` `'a'` `][freq[i]]);` ` ` `}` ` ` `System.out.print(` `"\n"` `);` ` ` `}` `}` `// Driver code` `public` `static` `void` `main(String []args)` `{` ` ` `String str = ` `"geeksforgeeks"` `;` ` ` `// Queries` ` ` `int` `type[] = { ` `1` `, ` `2` `};` ` ` `char` `ch[] = { ` `'e'` `, ` `'k'` `};` ` ` `int` `freq[] = { ` `2` `, ` `2` `};` ` ` `int` `q = type.length;` ` ` `// Perform the queries` ` ` `performQueries(str, q, type, ch, freq);` `}` `}` `// This code is contributed by Rajput-Ji` |

## Python3

`# Python3 implementation of the approach` `import` `numpy as np` `MAX` `=` `26` `;` `# Function to perform the queries` `def` `performQueries(string , q, type_arr, ch, freq) :` ` ` `n ` `=` `len` `(string);` ` ` `# L[i][j] stores the largest i` ` ` `# such that ith character appears` ` ` `# exactly jth times in str[0...i]` ` ` `L ` `=` `np.zeros((` `MAX` `, n));` ` ` `# F[i][j] stores the smallest i` ` ` `# such that ith character appears` ` ` `# exactly jth times in str[0...i]` ` ` `F ` `=` `np.zeros((` `MAX` `, n));` ` ` `# To store the frequency of each` ` ` `# of the character of str` ` ` `cnt ` `=` `[ ` `0` `] ` `*` `MAX` `;` ` ` `for` `i ` `in` `range` `(n) :` ` ` `# Current character of str` ` ` `k ` `=` `ord` `(string[i]) ` `-` `ord` `(` `'a'` `);` ` ` `# Update its frequency` ` ` `cnt[k] ` `+` `=` `1` `;` ` ` `# For every lowercase character` ` ` `# of the English alphabet` ` ` `for` `j ` `in` `range` `(` `MAX` `) :` ` ` `# If it is equal to the character` ` ` `# under consideration then update` ` ` `# L[][] and R[][] as it is cnt[j]th` ` ` `# occurrence of character k` ` ` `if` `(k ` `=` `=` `j) :` ` ` `L[j][cnt[j]] ` `=` `i;` ` ` `F[j][cnt[j]] ` `=` `i;` ` ` `# Only update L[][] as k has not` ` ` `# been occurred so only index` ` ` `# has to be incremented` ` ` `else` `:` ` ` `L[j][cnt[j]] ` `=` `L[j][cnt[j]] ` `+` `1` `;` ` ` `# Perform the queries` ` ` `for` `i ` `in` `range` `(q) :` ` ` `# Type 1 query` ` ` `if` `(type_arr[i] ` `=` `=` `1` `) :` ` ` `print` `(L[` `ord` `(ch[i]) ` `-` ` ` `ord` `(` `'a'` `)][freq[i]], end ` `=` `"");` ` ` `# Type 2 query` ` ` `else` `:` ` ` `print` `(F[` `ord` `(ch[i]) ` `-` ` ` `ord` `(` `'a'` `)][freq[i]], end ` `=` `"");` ` ` ` ` `print` `()` ` ` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `string ` `=` `"geeksforgeeks"` `;` ` ` `# Queries` ` ` `type_arr ` `=` `[ ` `1` `, ` `2` `];` ` ` `ch ` `=` `[ ` `'e'` `, ` `'k'` `];` ` ` `freq ` `=` `[ ` `2` `, ` `2` `];` ` ` `q ` `=` `len` `(type_arr);` ` ` `# Perform the queries` ` ` `performQueries(string, q, type_arr, ch, freq);` `# This code is contributed by AnkitRai01` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` `static` `int` `MAX = 26;` `// Function to perform the queries` `static` `void` `performQueries(String str, ` `int` `q, ` `int` `[]type,` ` ` `char` `[]ch, ` `int` `[]freq)` `{` ` ` `int` `n = str.Length;` ` ` `// L[i,j] stores the largest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `[,]L = ` `new` `int` `[MAX, n];` ` ` `// F[i,j] stores the smallest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `int` `[,]F = ` `new` `int` `[MAX, n];` ` ` `// To store the frequency of each` ` ` `// of the character of str` ` ` `int` `[]cnt = ` `new` `int` `[MAX];` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `// Current character of str` ` ` `int` `k = str[i] - ` `'a'` `;` ` ` `// Update its frequency` ` ` `cnt[k]++;` ` ` `// For every lowercase character` ` ` `// of the English alphabet` ` ` `for` `(` `int` `j = 0; j < MAX; j++)` ` ` `{` ` ` `// If it is equal to the character` ` ` `// under consideration then update` ` ` `// L[,] and R[,] as it is cnt[j]th` ` ` `// occurrence of character k` ` ` `if` `(k == j)` ` ` `{` ` ` `L[j, cnt[j]] = i;` ` ` `F[j, cnt[j]] = i;` ` ` `}` ` ` `// Only update L[,] as k has not` ` ` `// been occurred so only index` ` ` `// has to be incremented` ` ` `else` ` ` `L[j, cnt[j]] = L[j, cnt[j]] + 1;` ` ` `}` ` ` `}` ` ` `// Perform the queries` ` ` `for` `(` `int` `i = 0; i < q; i++)` ` ` `{` ` ` `// Type 1 query` ` ` `if` `(type[i] == 1)` ` ` `{` ` ` `Console.Write(L[ch[i] - ` `'a'` `, freq[i]]);` ` ` `}` ` ` `// Type 2 query` ` ` `else` ` ` `{` ` ` `Console.Write(F[ch[i] - ` `'a'` `, freq[i]]);` ` ` `}` ` ` `Console.Write(` `"\n"` `);` ` ` `}` `}` `// Driver code` `public` `static` `void` `Main(String []args)` `{` ` ` `String str = ` `"geeksforgeeks"` `;` ` ` `// Queries` ` ` `int` `[]type = { 1, 2 };` ` ` `char` `[]ch = { ` `'e'` `, ` `'k'` `};` ` ` `int` `[]freq = { 2, 2 };` ` ` `int` `q = type.Length;` ` ` `// Perform the queries` ` ` `performQueries(str, q, type, ch, freq);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` ` ` `// JavaScript implementation of the approach` ` ` ` ` `let MAX = 26;` ` ` ` ` `// Function to perform the queries` ` ` `function` `performQueries(str, q, type, ch, freq)` ` ` `{` ` ` `let n = str.length;` ` ` `// L[i][j] stores the largest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `let L = ` `new` `Array(MAX);` ` ` `// F[i][j] stores the smallest i` ` ` `// such that ith character appears` ` ` `// exactly jth times in str[0...i]` ` ` `let F = ` `new` `Array(MAX);` ` ` `// To store the frequency of each` ` ` `// of the character of str` ` ` `let cnt = ` `new` `Array(MAX);` ` ` ` ` `for` `(let i = 0; i < MAX; i++)` ` ` `{` ` ` `L[i] = ` `new` `Array(n);` ` ` `F[i] = ` `new` `Array(n);` ` ` `cnt[i] = 0;` ` ` `for` `(let j = 0; j < n; j++)` ` ` `{` ` ` `L[i][j] = 0;` ` ` `F[i][j] = 0;` ` ` `}` ` ` `}` ` ` ` ` `for` `(let i = 0; i < n; i++)` ` ` `{` ` ` `// Current character of str` ` ` `let k = str[i].charCodeAt() - ` `'a'` `.charCodeAt();` ` ` `// Update its frequency` ` ` `cnt[k]++;` ` ` `// For every lowercase character` ` ` `// of the English alphabet` ` ` `for` `(let j = 0; j < MAX; j++)` ` ` `{` ` ` `// If it is equal to the character` ` ` `// under consideration then update` ` ` `// L[][] and R[][] as it is cnt[j]th` ` ` `// occurrence of character k` ` ` `if` `(k == j)` ` ` `{` ` ` `L[j][cnt[j]] = i;` ` ` `F[j][cnt[j]] = i;` ` ` `}` ` ` `// Only update L[][] as k has not` ` ` `// been occurred so only index` ` ` `// has to be incremented` ` ` `else` ` ` `L[j][cnt[j]] = L[j][cnt[j]] + 1;` ` ` `}` ` ` `}` ` ` `// Perform the queries` ` ` `for` `(let i = 0; i < q; i++)` ` ` `{` ` ` `// Type 1 query` ` ` `if` `(type[i] == 1)` ` ` `{` ` ` `document.write(L[ch[i].charCodeAt() -` ` ` `'a'` `.charCodeAt()][freq[i]]);` ` ` `}` ` ` `// Type 2 query` ` ` `else` ` ` `{` ` ` `document.write(F[ch[i].charCodeAt() -` ` ` `'a'` `.charCodeAt()][freq[i]]);` ` ` `}` ` ` `document.write(` `"</br>"` `);` ` ` `}` ` ` `}` ` ` ` ` `let str = ` `"geeksforgeeks"` `;` ` ` ` ` `// Queries` ` ` `let type = [ 1, 2 ];` ` ` `let ch = [ ` `'e'` `, ` `'k'` `];` ` ` `let freq = [ 2, 2 ];` ` ` `let q = type.length;` ` ` ` ` `// Perform the queries` ` ` `performQueries(str, q, type, ch, freq);` `</script>` |

**Output:**

8 11

**Time Complexity:** O(n) where n is the length of the string.