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

2021年4月29日18:31:50 发表评论 760 次浏览

本文概述

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

  1. 1 C X：找到最大的一世这样str [0…i]完全有X角色的出现C.
  2. 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 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 = "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#

//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

输出如下：

8
11

时间复杂度：O(n)其中n是字符串的长度。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: