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:
Input: str = “neveropen”, query[] = {{1, ‘e’, 2}, {2, ‘k’, 2}}
Output:
8
11
Query 1: “neveropenforg” is the largest substring starting at str[0] with ‘e’ appearing exactly twice and the index of the last character is 8.
Query 2: “neveropenforgeek” 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 ith character appears exactly jth times in str[0…i] and F[i][j] stores the smallest i such that the ith character appears exactly jth times in 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 = "neveropen" ; // 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 = "neveropen" ; // 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 = "neveropen" ; # 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 = "neveropen" ; // 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 = "neveropen" ; // 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> |
8 11
Time Complexity: O(n)
Auxiliary Space: O(26 * n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!