Fácil-medio · cadenas
Compresión por longitud
Recorre la línea con un único puntero: el carácter sobre el que estás, cuenta cuántas veces se repite, escríbelo con su contador y ya has pasado el tramo entero. Sin bucles anidados sobre la cadena — el contador ES el bucle interno.
En una fraseAvanza con un índice: en cada posición cuenta el tramo de caracteres iguales, escribe el carácter y el contador (siempre, también 1 — a10 es legal), y continúa tras el tramo.
El problema
Entrada: Una línea de 1 a 200 letras minúsculas, sin espacios.
Salida: La codificación por longitud: para cada tramo maximal, el carácter seguido de su contador. El contador se escribe siempre, también cuando es 1.
Ejemplos:
| Entrada | Salida |
|---|---|
aaabbc | a3b2c1 |
a | a1 |
Los contadores llegan a dos cifras: un tramo de 10 letras iguales se escribe a10, dos caracteres de salida para un tramo de 10 — ese es todo el punto de comprimir.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — El tramo se cierra solo
Colócate en la posición i y cuenta mientras s[i] == c. Cuando el bucle de conteo sale, i ya apunta al primer carácter del siguiente tramo — no hay nada que saltar ni rebobinar; solo reiniciar el contador. Un puntero por toda la cadena, nunca hacia atrás.
Pista 2 — Los contadores se escriben como números
cout << contador maneja una, dos o tres cifras — no hace falta partir dígitos a mano, ese era el trabajo del problema de binario. Pero ojo con lo que sí exige: escribir el contador también cuando es 1. Dar abc para abc parece natural y está mal.
Pista 3 — Lee la línea entera
Una vuelta más a la lección de cin.getline: aquí no hay espacios, pero sigue siendo el lector correcto para una línea que hay que tomar entera — y no deja ningún Enter detrás que envenene una lectura posterior. El argumento completo está en Invertir el orden de las palabras.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
char s[205];
cin.getline(s, 205);
int i = 0;
while (s[i] != '\0') {
char c = s[i];
int count = 0;
while (s[i] == c) {
count++;
i++;
}
cout << c << count;
}
cout << endl;
return 0;
}La codificación por longitud es la antepasada de la compresión real (vive dentro del fax, JPEG y PNG), y aquí es además otra vez el patrón de autómata sobre cadenas: una bandera, un contador, sin mirar adelante. Su prima contadora — tramos de una *clase* en vez de tramos de un *carácter* — es Contar palabras.
Análisis profundo
Por qué funciona
Un único puntero hacia adelante con un conteo interno que se autotermina: en cuanto s[i] deja de ser c, i ya está en el siguiente tramo. Sin segundo índice, sin mirar adelante, sin segunda pasada — el contador es el bucle interno y la cadena segmenta sola.
El coste
O(L) de tiempo para una línea de L caracteres — cada carácter lo visita exactamente una vez el puntero exterior — y O(L) de espacio para la salida, que aquí nunca supera la entrada.
Dónde falla
- Omitir el contador cuando es 1 parece más limpio y está mal: la especificación dice escribirlo siempre, y 'a' debe salir como a1.
- Leer con
cin >>se pararía en el primer espacio (aquí no hay, pero el hábito importa) — y lo importante es que getline es el lector de línea entera que este formato presupone. - No hace falta separador entre el contador y el siguiente carácter — el formato es carácter seguido inmediatamente de dígitos.
Siguiente paso
El mismo escaneo de una bandera y un contador, contando tramos de una *clase* (espacios) en vez de de un carácter, es Contar palabras.
Dos cosas para recordar
- El bucle de conteo interno ES la segmentación — i aterriza gratis en el siguiente tramo.
- Escribe el contador siempre, también 1; cout maneja las cifras múltiples.
🐞 Esta versión falla: ábrela y pruébala
Se salta el contador cuando es 1 — el juez quiere a1, no a
#include <iostream>
using namespace std;
int main() {
char s[205];
cin.getline(s, 205);
int i = 0;
while (s[i] != '\0') {
char c = s[i];
int count = 0;
while (s[i] == c) {
count++;
i++;
}
cout << c;
if (count > 1) cout << count; // bug: count of 1 is required too
}
cout << endl;
return 0;
}