Índice de caracteres según el conteo de frecuencia en la string

Dada una string str que contiene solo caracteres en minúsculas, la tarea es responder consultas Q del siguiente tipo: 
 

1. 1 CX: Encuentre la i más grande tal que str[0…i] tenga exactamente X ocurrencias del carácter C .
2. 2 CX: Encuentre la i más pequeña tal que str[0…i] tenga exactamente X ocurrencias del carácter C .

Ejemplo: 
 

Entrada: str = “geeksforgeeks”, consulta[] = {{1, ‘e’, ​​2}, {2, ‘k’, 2}} 
Salida: 
8 
11 
Consulta 1: “geeksforg” es la substring más grande que comienza en str [0] con ‘e’ apareciendo exactamente dos veces y el índice del último carácter es 8. 
Consulta 2: «geeksforgeek» es la substring más pequeña que comienza en str[0] con ‘k’ apareciendo exactamente dos veces y el índice del último carácter es 11.
Entrada: str = “abcdabcd”, consulta[] = {{1, ‘a’, 1}, {2, ‘a’, 2}} 
Salida: 
3 
4 
 

Enfoque: cree dos arrays bidimensionales L[][] y F[][] de modo que L[i][j] almacene la i más grande de modo que el i ^-ésimo carácter aparezca exactamente j ^-ésimas veces en str[0…i] y F[i][j] almacena la i más pequeña tal que el i ^-ésimo carácter aparece exactamente j ^-ésimas veces en str[0…i] . Para hacerlo, recorra toda la string y mantenga una array de frecuencia para que, para cada iteración/carácter, se actualice su recuento y luego comience otro ciclo de 0 a26 (cada letra az). En el ciclo interno, si el iterador es igual al valor del carácter, actualice la array L[][] y F[][] con la posición del índice actual usando el iterador del ciclo externo; de lo contrario, simplemente incremente el valor de la array L[][] para otros caracteres en 1 ya que solo se ha incrementado el índice y no se ha producido el carácter. Ahora, la consulta de tipo 1 se puede responder como L[carácter dado][Recuento de frecuencia] y la consulta de tipo 2 como F[carácter dado][Recuento de frecuencia] .
A continuación se muestra la implementación del enfoque anterior. 
 

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

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

8
11

Complejidad de tiempo: O(n) donde n es la longitud de la string.