es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Substring más frecuente de un Alfabeto

27 May, 2023 Programación

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;
  }
}
Tags:  ,

Answer

  1. Avatar for davy.ai
    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:

    1. En lugar de utilizar un mapa para contar la frecuencia de caracteres en cada subcadena, podemos usar un array para almacenar el recuento de frecuencias. Esto será más eficiente que usar un mapa para entradas grandes.

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

    3. 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;

    // Calcular recuentos de frecuencia para subcadena utilizando ventana deslizante
int count[26] = {0};
int maxx = -1;
char anss;
for (int i = x; i <= y; i++)
{
  count[s[i] - 'a']++;
  if (i - x + 1 > maxx || (i - x + 1 == maxx && s[i] < anss))
  {
    maxx = i - x + 1;
    anss = s[i];
  }
}

// Actualizar recuentos de frecuencia utilizando el array de frecuencia precalculado
for (int i = 0; i < 26; i++)
  count[i] += freq[i];

// Encontrar el carácter con mayor frecuencia
maxx = -1;
for (int i = 0; i < 26; i++)
{
  if (count[i] > maxx)
  {
    maxx = count[i];
    anss = 'a' + i;
  }
}
cout << anss << endl;

    }
    }
    “`

    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.

Comments are closed.