Planteamiento del Problema

Se proporciona una cadena compuesta exclusivamente por letras minúsculas del alfabeto inglés. El objetivo es calcular la frecuencia de aparición de cada letra y determinar cuál es la más frecuente. En caso de que existan múltiples letras con la misma frecuencia máxima, se debe devolver aquella que tenga precedencia lexicográfica (es decir, la que aparezca primero en el alfabeto).

Formato de entrada:

La entrada consta de múltiples casos de prueba. Cada caso comienza con un número entero que indica la cantidad de cadenas a procesar, seguido de las cadenas correspondientes, cada una en una línea separada.

Formato de salida:

Para cada cadena procesada, se debe imprimir en una línea independiente el carácter que cumple con las condiciones descritas.

Ejemplo de entrada:

2
abcdeef
aabbccddeeff

Ejemplo de salida:

e
a

Fundamentos de las Tablas Hash

Una tabla hash es una esturctura de datos que permite el acceso directo a los elementos mediante una clave (key). Su propósito principal es verificar rápidamente la existencia de un elemento dentro de un conjunto. Esto se logra estableciendo una relación determinista entre la clave y su posición de almacenamiento a través de una función matemática conocida como función hash o de dispersión.

Para implementar tablas hash, generalmente se recurre a tres estructuras de datos fundamentales:

• Arreglos (Arrays)
• Conjuntos (set)
• Mapas o diccionarios (map)

Conceptualmente, una tabla hash funciona como un archivador con múltiples cajones numerados. La función hash transforma la clave en un índice numérico que apunta a un cajón específico donde se almacena el valor. Cuando surgen colisiones (diferentes claves que generan el mismo índice), se aplican estrategias de resolución para garantizar la integridad de los datos. La principal ventaja de esta estructura es su capacidad para realizar búsquedas, insercioens y eliminaciones en un tiempo promedio constante, O(1).

Uso de Arreglos como Tablas Hash

Dado que el problema restringe los caracteres a letras minúsculas del alfabeto inglés, el espacio de claves es finito y reducido (exactamente 26 caracteres). Esto convierte a un arreglo de tamaño fijo en la tabla hash más eficiente para este escenario.

Los caracteres en C++ están representados por sus valores ASCII, los cuales son consecutivos para las letras minúsculas ('a' hasta 'z'). Por lo tanto, podemos mapear cada letra a un índice del arreglo restando el valor ASCII de 'a' al valor ASCII del carácter actual. Así, 'a' se mapea al índice 0, 'b' al 1, y así sucesivamente hasta 'z' en el índice 25.

Al iterar sobre la cadena, simplemente incrementamos el contador en la posición correspondiente:

// Registro de frecuencias
for (char c : text) {
    frequencyMap[c - 'a']++;
}

Una vez poblado el arreglo, basta con recorrerlo de principio a fin (del índice 0 al 25). Al evaluar los valores con una condición de "estrictamente mayor" (>), nos aseguramos de que, en caso de empate, se conserve el carácter evaluado primero, garantizando así la precedencia lexicográfica requerida.

Implementación en C++

#include <iostream>
#include <string>
#include <vector>

int main() {
    // Optimización para acelerar las operaciones de entrada/salida estándar
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int testCases;
    // Lectura continua de casos de prueba
    while (std::cin >> testCases) {
        while (testCases--) {
            std::string inputText;
            std::cin >> inputText;
            
            // Arreglo que actúa como tabla hash para las 26 letras minúsculas
            std::vector<int> frequencyMap(26, 0);
            
            // Cálculo de frecuencias usando un bucle basado en rangos
            for (char currentChar : inputText) {
                frequencyMap[currentChar - 'a']++;
            }
            
            int maxFrequency = -1;
            char mostFrequentChar = 'a';
            
            // Búsqueda de la frecuencia máxima
            // Al iterar desde 0 hasta 25 y usar '>', garantizamos el orden lexicográfico en empates
            for (int i = 0; i < 26; ++i) {
                if (frequencyMap[i] > maxFrequency) {
                    maxFrequency = frequencyMap[i];
                    mostFrequentChar = static_cast<char>(i + 'a');
                }
            }
            
            std::cout << mostFrequentChar << '\n';
        }
    }
    
    return 0;
}