El grafito de Pompeya
- O(2ⁿ) · Legendaria
- Plan completo
- Python
- JavaScript
- recursión
- textos
- índices
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):
passJavaScript
function borrarMin(texto) {
}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ⁿ)
- El hilo de Ariadnarecursión · listas · ciclos
- El motivo escondidorecursión · textos · índices
- La balanza de dos platosrecursión · listas · operaciones
- La bodega de la cápsularecursión · listas · comparaciones
- La ficha de la abuelarecursión · listas · índices
- La fiesta de la cuadrarecursión · listas · ciclos