Substring más frecuente de un Alfabeto
Mi lógica funciona para entradas más pequeñas. ¿Cómo puedo mejorarla para aceptar entradas más grandes?
Pregunta:
El programa debe aceptar como entrada una cadena S que contenga solo letras minúsculas del alfabeto y Q consultas. Cada consulta
contiene dos enteros que representan los índices inicial y final de una subcadena en S. Para cada consulta, el
programa debe imprimir la letra más frecuente en la subcadena especificada. Si dos o más letras tienen
la misma frecuencia, entonces el programa debe imprimir la letra que es la menor en el orden alfabético.
Condición(es) límite:
2 <= Longitud de S <= 1000
1 <= Q <= 10^5
Ejemplo:
Entrada:
badbadbed
4
0 8
1 4
0 5
2 7
Salida:
b
a
a
b
<h1>include <bits/stdc++.h></h1>
usando espacio de nombres std;
int main(int argc, char** argv)
{
cadena s;
cin >> s;
int k;
cin >> k;
int x, y;
while (k--)
{
cin >> x >> y;
mapa<char, int>contador;
cadena ss = s.substr(x, y - x + 1);
set <char>muestras;
para (auto i : ss)
muestras.insertar(i);
int maxx = -1, st; char anss;
para (auto i : muestras)
si ((st = count(ss.begin(), ss.end(), i)) > maxx)
{
maxx = st;
anss = i;
}
cout << anss << endl;
}
}
davy.ai
Optimización de código para entradas más grandes
Para optimizar este código para entradas más grandes, podemos realizar los siguientes cambios:
Podemos pre-calcular un array de frecuencia para toda la cadena de entrada S. Esto nos permitirá calcular los recuentos de frecuencia para cada subcadena de manera más eficiente.
Podemos utilizar un enfoque de ventana deslizante para calcular los recuentos de frecuencia para cada subcadena. Esto evitará recalcular los recuentos de frecuencia para subcadenas que se superponen entre sí.
Aquí está el código optimizado:
“`c++
#include
using namespace std;
int main(int argc, char** argv)
{
string s;
cin >> s;
int k;
cin >> k;
// Precalcular array de frecuencia para toda la cadena de entrada
int freq[26] = {0};
for (auto i : s)
freq[i – ‘a’]++;
while (k–)
{
int x, y;
cin >> x >> y;
}
}
“`
El código optimizado utiliza un array para almacenar los recuentos de frecuencia para cada subcadena y precalcula el array de frecuencia para toda la cadena de entrada. También utiliza un enfoque de ventana deslizante para calcular los recuentos de frecuencia de manera eficiente.