Entrevista técnica: Mínimo de intercambios adyacentes para formar un palíndromo

Planteamiento y contexto

Cada intercambio adyacente tiene un costo de uno. Los caracteres pueden repetirse y la entrada puede ser imposible cuando más de un carácter tiene una frecuencia impar. El objetivo es el número mínimo de intercambios, no simplemente cualquier palíndromo.

Qué evalúa el entrevistador

• Deducir la condición de viabilidad basada en frecuencias impares.
• Emparejar el carácter de la izquierda con el compañero viable más cercano desde la derecha.
• Demostrar por qué la elección voraz es óptima y contabilizar los desplazamientos.

Preguntas de clarificación antes de responder

• ¿Los intercambios son únicamente adyacentes y cada intercambio cuesta uno?
• ¿El alfabeto es arbitrario y los puntos de código Unicode se tratan como caracteres?
• ¿La función debe mutar un arreglo o devolver solo el recuento?
• ¿Qué tamaño de entrada determina si un enfoque O(n²) es aceptable?

Estructura de respuesta en 30 segundos

Cuenta primero las frecuencias impares; más de un conteo impar hace que el palíndromo sea imposible. Usa punteros en ambos extremos. Si los extremos coinciden, avanza hacia el interior. De lo contrario, busca el carácter que coincida con el extremo izquierdo escaneando desde el límite derecho hacia adentro, llévalo hacia la derecha mediante intercambios adyacentes (burbujeo) y cuenta cada movimiento. Si no existe coincidencia, el carácter no emparejado debe ser el centro único; muévelo hacia el centro y continúa.

Análisis detallado paso a paso

1. Demostrar la viabilidad

Un palíndromo tiene a lo sumo una frecuencia impar, porque los pares ocupan posiciones simétricas y solo el centro de una longitud impar puede quedar sin emparejar. Esta comprobación evita ejecutar el bucle voraz en una entrada imposible.

2. Emparejar los límites

Para los punteros i y j, si s[i] es igual a s[j], ambas posiciones quedan fijas. De lo contrario, busca k desde j hacia abajo hasta i + 1 que sea igual a s[k] == s[i]. Mover ese carácter hacia la derecha cuesta j - k intercambios y preserva el prefijo ya fijado.

3. Manejar el carácter central

Si no se encuentra coincidencia, s[i] es el carácter de frecuencia impar que pertenece al centro. Muévelo un paso a la derecha a la vez hasta que llegue al medio, contando los intercambios. No lo descartes ni asumas que el centro debe encontrarse en la primera pasada.

4. Implementar la simulación

count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
    if s[left] == s[right]: left++, right--; continue
    k = right
    while k > left and s[k] != s[left]: k--
    if k == left:
        swap s[k] with s[k + 1]
        swaps++
    else:
        while k < right:
            swap s[k] with s[k + 1]
            k++, swaps++
        left++, right--
return swaps

5. Analizar la complejidad y la idea de la demostración

Cada pasada de búsqueda y burbujeo puede escanear O(n), repitiéndose O(n) veces, por lo que el tiempo es O(n²) y el arreglo mutable utiliza O(1) de espacio adicional. El compañero voraz es el más cercano al límite; mover un carácter igual más lejano requeriría al menos la misma cantidad de intercambios antes de que se pueda fijar el límite. El caso del centro viene forzado por la paridad.

Respuesta de ejemplo de alta calidad

“Primero cuento las frecuencias impares; más de una significa que es imposible. Luego comparo los dos extremos. Ante un desajuste, encuentro el carácter igual más cercano al límite derecho y lo desplazo hasta su posición, sumando su distancia; si no existe un igual, ese carácter es el centro impar único, por lo que lo muevo hacia el medio. Los extremos coincidentes reducen la ventana. La simulación toma O(n²) de tiempo y O(1) de espacio adicional, y la elección voraz es óptima porque cualquier compañero más lejano necesita al menos la misma cantidad de intercambios adyacentes”.

Errores comunes

• Verificar únicamente si los conteos son pares → las cadenas de longitud impar pueden tener un conteo impar → permite a lo sumo una frecuencia impar.
• Intercambiar con un carácter coincidente arbitrario → el movimiento adicional puede no ser mínimo → elige el compañero más cercano al límite.
• Descartar el carácter no emparejado → el movimiento al centro se subcuenta → llévalo hacia el medio mediante burbujeo.
• Usar intercambios de dos punteros sin desplazar → se pierde el costo del intercambio adyacente → simula cada movimiento adyacente o usa una estructura de datos equivalente.

Preguntas de seguimiento y respuestas

¿Puede el algoritmo devolver también el palíndromo?

Sí. Mantén el arreglo mutable y devuelve tanto su contenido final como el recuento de intercambios. La misma simulación registra cada intercambio adyacente si quien llama necesita la secuencia.

¿Cómo lo mejorarías para entradas grandes?

Rastrea las posiciones originales con un Fenwick tree o una estructura de estadísticas de orden para que mover un carácter pueda actualizar las posiciones en tiempo logarítmico. El emparejamiento voraz se mantiene, mientras que el cálculo de costos evita desplazar cada elemento.

¿Qué pasa si los intercambios son arbitrarios en lugar de adyacentes?

Ese es un modelo de costos diferente. La demostración de la distancia al compañero más cercano ya no aplica; define la operación permitida antes de reutilizar este algoritmo.