Remove Adjacent Duplicates II

Descripción del Problema

El problema, conocido como Remove All Adjacent Duplicates in String II (Eliminar Todos los Duplicados Adyacentes en una Cadena II), nos presenta una cadena de texto s y un número entero k.

El objetivo es eliminar grupos de k letras adyacentes e iguales de la cadena. Esta operación se debe realizar repetidamente: al eliminar un grupo, las partes restantes de la cadena se concatenan (se unen), lo que podría formar nuevos grupos de k duplicados que también deben ser eliminados.

Ejemplo:

Dada la cadena s = {"deeedbbcccbdaa"} y k = 3

Las eliminaciones ocurren en este orden:

1. Se encuentra "eee" (3 letras iguales). Se eliminan. La cadena queda: "ddbbcccbdaa".
2. Ahora se unen los lados y se encuentra "ccc". Se eliminan. La cadena queda: "ddbbbbdaa".
3. Al unirse de nuevo, se forman "bbb". Se eliminan. La cadena queda: "dddaa".
4. Finalmente, se forman "ddd". Se eliminan.

Salida esperada: "aa".

La Observación Clave (El "Insight")

Para simplificar el problema, se propone no intentar una solución de fuerza bruta (escanear repetidamente la cadena desde el inicio cada vez que se borra algo), ya que esto resultaría en una complejidad de tiempo cuadrática O(N^2), lo cual es ineficiente.

La observación fundamental es: No necesitamos re-escanear la cadena si recordamos la frecuencia del último carácter visto.

Si utilizamos una estructura de datos que nos permita recordar qué carácter vimos anteriormente y cuántas veces ha aparecido consecutivamente, podemos tomar decisiones en tiempo real.

Conclusión: Podemos utilizar una Pila (Stack) donde cada elemento no sea solo el carácter, sino un par o estructura: {carácter, conteo}.

La Estrategia de Solución

Una vez que decidimos usar una pila para procesar los caracteres de izquierda a derecha, la lógica es la siguiente:

• Recorremos la cadena s carácter por carácter.
• Para cada carácter actual, miramos el tope de la pila:
• Si la pila no está vacía y el carácter actual es igual al del tope, incrementamos el contador de ese elemento en la pila.
• Si el carácter es diferente (o la pila está vacía), insertamos un nuevo elemento {carácter, 1}.

El momento de la eliminación: Inmediatamente después de incrementar un contador, verificamos si este ha llegado a k.

Si el contador es igual a k, significa que hemos encontrado los k duplicados. Hacemos pop (eliminamos el elemento de la pila).

Solución Paso a Paso (Código)

struct Item { 
    char c; 
    int freq; 
};

string removeDuplicates(string s, int k) {
    vector<Item> items; 

    for (char c : s) {
        if (!items.empty() && items.back().c == c) {
            Item& current = items.back(); 
            if (current.freq + 1 == k) {
                items.pop_back();
            } else {
                current.freq++;
            }
        } else {
            items.push_back({c, 1});
        }
    }

    string ans = "";
    for (auto item : items) {
        ans.append(item.freq, item.c);
    }
    return ans;
}

Análisis de Complejidad

• Tiempo: O(N). Un solo recorrido del string.
• Espacio: O(N). Uso de la pila para almacenar caracteres.

Escrito por Elvis Rusnel Capia Quispe