Medio · dos punteros

Cadena palíndromo

Ya sabes recorrer una cadena al revés para invertirla. Ahora recórrela desde los dos extremos a la vez, y detente en la primera diferencia: un contraejemplo basta.

En una fraseAvanza dos índices desde los extremos hacia el centro e imprime yes si nunca discrepan: la palabra va en minúsculas y sin espacios, así que no hace falta normalizar.

El problema

Entrada: Una línea con una sola palabra de letras minúsculas, como máximo 100 caracteres, sin espacios.

Salida: yes si la palabra se lee igual en ambos sentidos; si no, no.

Ejemplos:

Entrada	Salida
`racecar`	`yes`
`hello`	`no`
`a`	`yes`

Un solo carácter es trivialmente un palíndromo, y una comparación vacía también. Por eso aquí la condición del bucle importa más que el cuerpo.

Tu solución

main.cpp — 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 — La versión ingenua son dos pasadas; basta con una

Podrías copiar la cadena, invertirla y comparar: O(n) de tiempo y O(n) de memoria extra. Pero un palíndromo es simétrico, así que puedes comprobarlo en el sitio: el carácter 0 contra el n−1, el 1 contra el n−2, y así. Sin copia.

Pista 2 — Dos índices, una condición

int i = 0, j = n - 1; y luego while (i < j). Compara s[i] con s[j]; si difieren, activa una bandera y haz break; si no, i++ y j--. La condición i < j es lo que hace funcionar las palabras de longitud impar: el carácter central se compara consigo mismo y pasaría igual.

Pista 3 — El error de uno que muerde

El espejo del índice i es n - 1 - i, no n - i. Si lo escribes mal comparas cada carácter con su vecino de la derecha, y además lees un byte más allá del final, que resulta ser el terminador '\0': la respuesta se vuelve incorrecta en silencio en vez de fallar.

Solución (¡inténtalo primero!)

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[105];
    cin >> s;
    int n = strlen(s);

    int i = 0, j = n - 1;
    bool ok = true;
    while (i < j) {
        if (s[i] != s[j]) {
            ok = false;
            break;
        }
        i++;
        j--;
    }

    if (ok) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

Dos índices que se acercan es el patrón detrás de bastante más de lo que parece: comprobar si un array está ordenado, eliminar duplicados en el sitio, encontrar en un array ordenado un par que sume un objetivo, y el paso de partición de quicksort. La razón por la que funciona es siempre la misma: los datos tienen una simetría, y dos punteros te dejan explotarla sin memoria extra. Ahora lleva la misma idea de "leer la forma, no el orden" a una rejilla: Transponer una matriz.

Análisis profundo

Por qué funciona

Dos índices avanzan uno hacia el otro y cada paso compara un par espejado. La cadena tiene una simetría, y dos punteros son cómo la aprovechas sin copiar nada.

El coste

O(n) de tiempo y O(1) de memoria, y se detiene en la primera diferencia. Copiar, invertir y comparar también es O(n) de tiempo, pero necesita O(n) de memoria para una copia que nunca querías.

Dónde falla

Escribir el espejo como n - i en vez de n - 1 - i compara cada carácter con su vecino derecho y lee un byte más allá del final, que resulta ser el terminador '\0': la respuesta falla en silencio en vez de romperse.
Usar i <= j es inofensivo pero inútil: el carácter central acaba comparándose consigo mismo. Usar i < n es peor: compara cada par dos veces.

Siguiente paso

La misma idea con otra forma: leer la estructura de una rejilla en vez de su orden: Transponer una matriz.

Dos cosas para recordar

Dos índices que se acercan, un par espejado por paso.
El espejo de i es n - 1 - i, no n - i.

🐞 Esta versión falla: ábrela y pruébala

Espejo escrito como n - i: compara cada carácter con su vecino derecho

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[105];
    cin >> s;
    int n = strlen(s);
    bool ok = true;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i]) ok = false;
    }
    if (ok) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}