Consultas para encontrar la primera aparición de un carácter en un rango dado

Dada una string S de longitud N y un arreglo Q[][] de dimensión M × 3 que consta de consultas de tipo {L, R, C} , la tarea es imprimir el primer índice del carácter C en el rango [L , R] , si se encuentra. De lo contrario, imprima -1.

Ejemplos:

Entrada: S= “abcabcabc”, Q[][] = { { 0, 3, ‘a’ }, { 0, 2, ‘b’ }, { 2, 4, ‘z’ } }
Salida: 0 1 – 1
Explicación:

• Primera consulta: imprime 0, que es el primer índice del carácter ‘a’ en el rango [0, 3].
• Segunda consulta: Imprimir 1, que es el primer índice del carácter ‘b’ en el rango [0, 2].
• Tercera consulta: imprima -1 ya que el carácter ‘z’ no aparece en el rango [2, 4].

Entrada: S= “geeksforgeeks”, Q[][] = { { 0, 12, ‘f’ }, { 0, 2, ‘g’ }, { 6, 12, ‘f’ } }
Salida: 5 0 – 1
Explicación: 

• Primera consulta: Imprimir 5, que es el primer índice del carácter ‘f’ en el rango [0, 12].
• Segunda consulta: Imprima 0, que es 
  el primer índice del carácter ‘g’ en el rango [0, 2].
• Tercera consulta: imprima -1 ya que el carácter ‘f’ no aparece en el rango [6, 12].

Enfoque ingenuo: el enfoque más simple es atravesar la string sobre el rango de índices [L, R] para cada consulta e imprimir la primera aparición del carácter C si se encuentra. De lo contrario, imprima -1 . 
Tiempo Complejidad: O(M * Q)
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar almacenando previamente los índices de caracteres en el mapa de vectores y utilizando la búsqueda binaria para encontrar el índice en el rango [L, R] en el vector de caracteres C . Siga los pasos a continuación para resolver el problema:

• Inicialice un Map < char, vector < int > > , digamos V , para almacenar índices de todas las apariciones de un carácter.
• Atraviese la string y actualice V .
• Atraviesa la array Q :
  • Si el tamaño de V[C] es cero, imprima -1.
  • De lo contrario, busque el índice utilizando la búsqueda binaria en el vector V[C], es decir , lower_bound(V[C].begin(), V[C].end(), L) – V[C].begin() y guárdelo en una variable, digamos idx .
  • Si idx = N o idx > R , imprima -1 .
  • De lo contrario, imprima el índice idx .

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation
// for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the first occurrence
// for a given range
int firstOccurrence(string s,
                   vector<pair<pair<int, int>, char> > Q)
{
    // N = length of string
    int N = s.size();
 
    // M = length of queries
    int M = Q.size();
 
    // Stores the indices of a character
    map<char, vector<int> > v;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
        // Push the index i
        // into the vector[s[i]]
        v[s[i]].push_back(i);
    }
 
    // Traverse the query
    for (int i = 0; i < M; i++) {
 
        // Stores the value L
        int left = Q[i].first.first;
 
        // Stores the value R
        int right = Q[i].first.second;
 
        // Stores the character C
        char c = Q[i].second;
 
        if (v.size() == 0) {
            cout << "-1 ";
            continue;
        }
 
        // Find index >= L in
        // the vector v
        int idx
            = lower_bound(v.begin(),
                          v.end(), left)
              - v.begin();
 
        // If there is no index of C >= L
        if (idx == (int)v.size()) {
 
            cout << "-1 ";
            continue;
        }
 
        // Stores the value at idx
        idx = v[idx];
 
        // If idx > R
        if (idx > right) {
            cout << "-1 ";
        }
 
        // Otherwise
        else {
            cout << idx << " ";
        }
    }
}
 
// Driver Code
int main()
{
    string S = "abcabcabc";
    vector<pair<pair<int, int>, char> > Q
        = { { { 0, 3 }, 'a' },
            { { 0, 2 }, 'b' },
            { { 2, 4 }, 'z' } };
 
    firstOccurrence(S, Q);
    return 0;
}

# Python3 implementation
# for the above approach
from bisect import bisect_left
 
# Function to find the first occurrence
# for a given range
def firstOccurrence(s, Q):
   
    # N = length of string
    N = len(s)
 
    # M = length of queries
    M = len(Q)
 
    # Stores the indices of a character
    v = [[] for i in range(26)]
 
    # Traverse the string
    for i in range(N):
 
        # Push the index i
        # into the vector[s[i]]
        v[ord(s[i]) - ord('a')].append(i)
 
    # Traverse the query
    for i in range(M):
 
        # Stores the value L
        left = Q[i][0]
 
        # Stores the value R
        right = Q[i][1]
 
        # Stores the character C
        c = Q[i][2]
 
        if (len(v[ord(c) - ord('a')]) == 0):
            print ("-1")
            continue
 
        # Find index >= L in
        # the vector v
        idx = bisect_left(v[ord(c) - ord('a')], left)
 
        # If there is no index of C >= L
        if (idx == len(v[ord(c) - ord('a')])):
            print("-1 ")
            continue
 
        # Stores the value at idx
        idx = v[ord(c) - ord('a')][idx]
 
        # If idx > R
        if (idx > right):
            print ("-1 ")
             
        # Otherwise
        else:
            print(idx, end=" ")
 
# Driver Code
if __name__ == '__main__':
    S = "abcabcabc";
    Q = [ [ 0, 3 , 'a'],[ 0, 2 , 'b' ],[ 2, 4, 'z']]
 
    firstOccurrence(S, Q)
 
    # This code is contributed by mohit kumar 29.

0 1 -1

Complejidad de tiempo: O(M * log(N))
Espacio auxiliar: O(N)