根据字符串中频率计数的字符索引 _数据结构

本文概述

C ++
Java
Python3
C#

给定一个字符串str仅包含小写字符, 任务是回答问以下类型的查询：

1 C X：找到最大的一世这样str [0…i]完全有X角色的出现C.
2 C X：找到最小的一世这样str [0…i]完全有X角色的出现C.

例子：

输入：str ="geeksforgeeks", query [] = {{1, 'e', 2}, {2, 'k', 2}}
输出：8 11
查询1："geeksforg"是从str开始的最大子串[0], " e"恰好出现两次, 最后一个字符的索引是8。
查询2："geeksforgeek"是从str [0]开始的最小子串, " k"恰好出现了两次, 最后一个字符的索引是11。
输入：str =" abcdabcd", query [] = {{1, 'a', 1}, {2, 'a', 2}}
输出：3 4

创建两个二维数组L[][]和F[][]，使L[i][j]存储最大的i，使第i个字符恰好出现在str[0…i]中第j次，F[i][j]存储最小的i，使第i个字符恰好出现在str[0…i]中第j次。为了做到这一点，遍历整个字符串并维护一个频率数组，以便对每个迭代/字符更新其计数，然后开始从0到26(每个字母a-z)的另一个循环。内循环,如果迭代器=字符值然后更新L F[][]和[][]数组当前索引位置使用外循环迭代器否则就增加L[][]数组值为其他角色1只指数递增,性格并没有发生。现在，类型1的查询可以回答为L[给定字符][频率计数]，类型2的查询可以回答为F[给定字符][频率计数]。
下面是上述方法的实现。
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 = "lsbin" ; //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 = "lsbin" ; //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 npMAX = 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 = "lsbin" ; # 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# 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 = "lsbin" ; //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

输出如下：