Saltar al contenido

El grafito de Pompeya

Enunciado

Lucio pinta anuncios en los muros de Pompeya, y un vecino le apostó que no era capaz de dejar en la pared algo que se leyera igual al derecho y al revés. Lucio no va a pintar nada nuevo: va a borrar letras de un grafito que ya está, sin mover las que quedan, hasta que lo que quede se lea igual en los dos sentidos. Cada letra borrada es trabajo, así que quiere borrar las menos posibles.

Recibes texto, las letras del grafito, en minúsculas y sin espacios (de 0 a 12 letras). Puedes borrar letras de cualquier lugar, no solo de las orillas, y las que quedan conservan su orden. Regresa, como entero, cuántas letras hay que borrar como mínimo para que lo que queda se lea igual al revés. Un texto vacío o de una sola letra ya se lee igual al revés.

Con "salinas" borras la l y la i, queda "sanas" y regresas 2. Con "acta" basta con borrar la c o la t: regresas 1. Con "radar" no hay nada que borrar: regresas 0.

Ejemplos

  • El primer ejemplo

    "salinas" → 2

  • El segundo ejemplo

    "acta" → 1

  • Ya se lee igual

    "radar" → 0

  • La letra de sobra está al final

    "aab" → 1

Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.

Empiezas con esto

Python

def borrar_min(texto):
    pass

JavaScript

function borrarMin(texto) {
}
Resolver este reto

Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.

Más retos de O(2ⁿ)

Ver todos los retos →