Problema: Super Reduced String (facil/easy)


  • administrators

    Nota: si aun no sabes usar Arrays de Caracteres/Cadenas te invito a leer el siguiente enlace Arrays en C++ (basico)

    Problema: Super Reduced String (facil/easy)

    En este problema te dan una cadena a la cual tienes que ir eliminando todos los pares de caracteres que vayas encontrando, mientras aun tenga pares debes seguir reduciendo la cadena.

    Entrada:

    Una cadena s de caracteres en una linea. La cadena s solo contiene letras y la longitud es menor o igual que 100, $1 < |s| \leq 100$

    Salida

    La cadena de caracteres sin ningún par de caracteres continuo.

    Ejemplo

    Si nos dan de entrada la siguiente cadena daacbbcdxyxy despues de ir eliminando los pares de caracteres seguidos como resultado tiene que imprimir xyxy.

    inicial:       daacbbcdxyxy
    eliminacion 1: d(aa)c(bb)cdxyxy -> dccdxyxy
    eliminacion 2: d(cc)dxyxy -> ddxyxy
    eliminacion 3: (dd)xyxy -> xyxy
    resultado:     xyxy
    

    Solucion

    En este problem lo único que necesitamos es recorrer la cadena e ir eliminando los caracteres continuos iguales. Para eliminar los caracteres simplemente iremos copiando la cadena antigua en una nueva pero saltandonos los caracteres iguales continuos.

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <fstream>
    
    using namespace std;
    
    char s[101];
    char auxS[101];
    
    int main() {
        gets(s);
        int n;
        bool hayMasCambios = true;
        while (hayMasCambios) {
            hayMasCambios = false; // si no existen cambios terminar ciclo
            n = strlen(s); // actual tamaño de s
            int itS = 0;
            for (int i = 0; i < n ; i++) { // recorrer s
                if (i + 1 < n) {
                    if (s[i] == s[i + 1]) {
                        i++; // saltar caracteres iguales continuos
                        hayMasCambios = true; // aun es posible mas reduccion ?
                    }
                    else {
                        auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada
                    }
                }
                else {
                    auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada
                }
            }
            auxS[itS] = '\0'; // aumentar 0 al final de la cadena limitando su tamaño
            strcpy(s, auxS); // copiar auxS -> s
        }
        if (n == 0) {
            cout << "Empty String\n";
        }
        else {
            cout << s << "\n";
        }
        return 0;
    }
    

    Enlace Original del problema: HackerRank - Super Reduced String (english)