Definición del Problema

Dado un arreglo de cadenas de texto, el objetivo es agrupar los anagramas. Un anagrama se define como una palabra o frase formada al reordenar las letras de una palabra o frase distinta, utilizando exactamente los mismos caracteres y la misma cantidad de veces.

Enfoque Inicial: Comparación de Frecuencias

Una aproximación directa al problema es iterar sobre cada cadena y compararla con los grupos ya formados. Para verificar si dos palabras son anagramas, se puede construir un mapa de frecuencias de sus caracteres. Sin embargo, evaluar cada nueva palabra contra todos los grupos existentes genera una complejidad cuadrática que suele resultar en un error de Time Limit Exceeded (Límite de Tiempo Excedido) al procesar volúmenes grandes de datos.

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

using namespace std;

vector<vector<string>> agruparAnagramasIneficiente(vector<string>& palabras) {
    vector<vector<string>> resultado;
    vector<unordered_map<char, int>> historialFrecuencias;

    for (const string& palabra : palabras) {
        int indiceGrupo = -1;
        unordered_map<char, int> freqActual;
        
        for (char c : palabra) {
            freqActual[c]++;
        }

        for (size_t i = 0; i < resultado.size(); ++i) {
            // Comparación rápida de longitud antes de evaluar el mapa
            if (resultado[i][0].length() == palabra.length()) {
                if (historialFrecuencias[i] == freqActual) {
                    indiceGrupo = i;
                    break;
                }
            }
        }

        if (indiceGrupo == -1) {
            resultado.push_back({palabra});
            historialFrecuencias.push_back(freqActual);
        } else {
            resultado[indiceGrupo].push_back(palabra);
        }
    }
    return resultado;
}

Solución Optimizada: Claves Canónicas con Tablas Hash

Para evitar las comparaciones anidadas, podemos transformar cada cadena en una representación canónica. Dado que todos los anagramas comparten exactamente los mismos caracteres, al ordenarlos alfabéticamente producirán la misma cadena resultante. Esta cadena ordenada actúa como un identificador único (clave) para agrupar las palabras originales.

Utilizando std::unordered_map, podemos mapear cada clave ordenada directamente a un vector de cadenas. Esta estrategia elimina la necesidad de estructuras como std::multiset y optimiza la construcción del resultado final mediante semántica de moviimento.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<string>> agruparAnagramasOptimo(vector<string>& listaPalabras) {
    unordered_map<string, vector<string>> gruposAnagramas;
    
    for (const string& palabra : listaPalabras) {
        string claveOrdenada = palabra;
        sort(claveOrdenada.begin(), claveOrdenada.end());
        gruposAnagramas[claveOrdenada].push_back(palabra);
    }
    
    vector<vector<string>> resultadoFinal;
    resultadoFinal.reserve(gruposAnagramas.size());
    
    for (auto& par : gruposAnagramas) {
        resultadoFinal.push_back(move(par.second));
    }
    
    return resultadoFinal;
}

int main() {
    vector<string> entrada = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> salida = agruparAnagramasOptimo(entrada);
    
    for (const auto& grupo : salida) {
        for (const auto& palabra : grupo) {
            cout << palabra << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Análisis de Complejidad y Estructuras de Datos

• Dominio de la STL: La implementación óptima demuestra la versatilidad de la Biblioteca Estándar de C++. Aplicar std::sort directamente sobre los iteradores de un std::string simplifica drásticamente la lógica de validación de anagramas.
• Mejora en la Complejidad Temporal: Al reemplazar las búsquedas lineales por inserciones en una tabla hash, la complejidad se reduce de $O(N^2 \cdot K)$ a $O(N \cdot K \log K)$, donde $N$ representa la cantidad total de cadenas y $K$ la longitud máxima de una cadena.
• Gestión de Memoria: El uso de std::move al transferir los vectores desde el mapa hacia el arreglo de resultados evita copias innecesarias de cadenas, mejorando el rendimiento general en tiempo de ejecución.