Número de veces que la string dada aparece en la array en el rango [l, r]

Dada una array de strings arr[] y dos enteros l y r , la tarea es encontrar la cantidad de veces que la string dada str aparece en la array en el rango [l, r] (indexación basada en 1). Tenga en cuenta que las strings contienen solo letras minúsculas.
Ejemplos: 
 

Entrada: arr[] = {“abc”, “def”, “abc”}, L = 1, R = 2, str = “abc” 
Salida: 1
Entrada: arr[] = {“abc”, “def” , “abc”}, L = 1, R = 3, str = “ghf” 
Salida: 0 
 

Enfoque: la idea es utilizar un mapa_desordenado para almacenar los índices en los que aparece la i-ésima string de array. Si la string dada no está presente en el mapa, la respuesta es cero; de lo contrario, realice una búsqueda binaria en los índices de la string dada presente en el mapa y encuentre el número de ocurrencias de la string en el rango [L, R].
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of occurrences of
int NumOccurrences(string arr[], int n, string str, int L, int R)
{
    // To store the indices of strings in the array
    unordered_map<string, vector<int> > M;
    for (int i = 0; i < n; i++) {
        string temp = arr[i];
        auto it = M.find(temp);
 
        // If current string doesn't
        // have an entry in the map
        // then create the entry
        if (it == M.end()) {
            vector<int> A;
            A.push_back(i + 1);
            M.insert(make_pair(temp, A));
        }
        else {
            it->second.push_back(i + 1);
        }
    }
 
    auto it = M.find(str);
 
    // If the given string is not
    // present in the array
    if (it == M.end())
        return 0;
 
    // If the given string is present
    // in the array
    vector<int> A = it->second;
    int y = upper_bound(A.begin(), A.end(), R) - A.begin();
    int x = upper_bound(A.begin(), A.end(), L - 1) - A.begin();
 
    return (y - x);
}
 
// Driver code
int main()
{
    string arr[] = { "abc", "abcabc", "abc" };
    int n = sizeof(arr) / sizeof(string);
    int L = 1;
    int R = 3;
    string str = "abc";
 
    cout << NumOccurrences(arr, n, str, L, R);
 
    return 0;
}

# Python implementation of the approach
from bisect import bisect_right as upper_bound
from collections import defaultdict
 
# Function to return the number of occurrences of
def numOccurences(arr: list, n: int, string: str, L: int, R: int) -> int:
 
    # To store the indices of strings in the array
    M = defaultdict(lambda: list)
    for i in range(n):
        temp = arr[i]
 
        # If current string doesn't
        # have an entry in the map
        # then create the entry
        if temp not in M:
            A = []
            A.append(i + 1)
            M[temp] = A
        else:
            M[temp].append(i + 1)
 
    # If the given string is not
    # present in the array
    if string not in M:
        return 0
 
    # If the given string is present
    # in the array
    A = M[string]
    y = upper_bound(A, R)
    x = upper_bound(A, L - 1)
 
    return (y - x)
 
# Driver Code
if __name__ == "__main__":
    arr = ["abc", "abcabc", "abc"]
    n = len(arr)
    L = 1
    R = 3
    string = "abc"
 
    print(numOccurences(arr, n, string, L, R))
 
# This code is contributed by
# sanjeev2552

2

Complejidad de tiempo: O(N), 
Espacio auxiliar: O(N)