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

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

本文概述

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

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