Entrevista técnica: ¿Cómo calcular la distancia de edición con programación dinámica?

Problema y escenarios aplicables

Dadas dos cadenas source y target, devuelve el número mínimo de ediciones necesarias para transformar source en target. Una edición inserta un carácter, elimina un carácter o reemplaza un carácter. Cada operación cuesta uno. Cualquiera de las cadenas puede estar vacía y ambas contienen únicamente letras minúsculas en inglés.

source = "horse"
target = "ros"

horse -> rorse   replace h with r
rorse -> rose    delete r
rose  -> ros     delete e

answer = 3

Sean m = source.length y n = target.length, con ambas longitudes como máximo de 2,000. La tarea solo pide el costo mínimo, no un script de edición. El artículo de Wagner–Fischer define la corrección de cadenas como una secuencia de costo mínimo de inserciones, eliminaciones y sustituciones, y proporciona un algoritmo cuyo tiempo es proporcional al producto de las dos longitudes. Las guías de entrevistas actuales de 2026 todavía utilizan la distancia de edición como un ejercicio canónico de programación dinámica con dos cadenas. Esto respalda el valor de preparación del tema; no demuestra la frecuencia ni la atribución a una empresa en particular.

Este problema aparece en correctores ortográficos, búsqueda difusa (fuzzy matching), vinculación de registros y comparación de secuencias, pero las definiciones de producción pueden utilizar operaciones ponderadas, transposiciones, normalización o tokens específicos del dominio. La versión de entrevista fija deliberadamente ediciones de caracteres de costo unitario para que su estado y su demostración sean inequívocos.

Qué evalúa el entrevistador

La primera señal es una definición de estado con límites exactos. Definir dp[i][j] como el mínimo de ediciones necesarias para convertir los primeros i caracteres de source en los primeros j caracteres de target. “La respuesta hasta i y j” es demasiado vaga para justificar una transición o inicializar un prefijo vacío.

La segunda señal es deducir las tres transiciones de caracteres que no coinciden. La operación final de una solución óptima debe ser una de eliminar, insertar o reemplazar. Eliminar esa operación final deja un problema de prefijo más pequeño. El candidato debe mapear cada operación a la celda vecina correcta en lugar de memorizar tres coordenadas.

La tercera señal es manejar los caracteres finales coincidentes sin inventar trabajo. Si source[i - 1] es igual a target[j - 1], una solución óptima puede dejar ese carácter sin cambios, por lo que el valor proviene de dp[i - 1][j - 1]. La demostración también debe mostrar que no se oculta ninguna solución más económica con esta elección.

La cuarta señal es reconocer la forma de la dependencia. Una fila usa solo la fila anterior y su propia celda izquierda, por lo que la matriz completa de O(mn) es innecesaria cuando solo se devuelve la distancia. Colocar la cadena más corta en la dimensión de las columnas proporciona un espacio auxiliar de O(min(m, n)).

La señal final es preservar el contrato del problema. Intercambiar las cadenas de filas y columnas es válido aquí porque la inserción y eliminación de costo unitario hacen que la distancia sea simétrica. No es automáticamente válido cuando la inserción y la eliminación tienen pesos diferentes. El texto Unicode también requiere una elección explícita entre unidades de código UTF-16, puntos de código Unicode y grupos de grafemas percibidos por el usuario.

Preguntas para aclarar antes de responder

• ¿Qué operaciones están permitidas? Este problema permite inserción, eliminación y reemplazo. La transposición

adyacente no es una operación única.

• ¿Cuánto cuesta una edición? Cada operación permitida cuesta uno. Los costos ponderados cambian la recurrencia y pueden

eliminar la simetría.

• ¿Cuál es la unidad de comparación? La consigna utiliza letras minúsculas en inglés, por lo que la indexación de JavaScript es segura para

esta implementación. El texto Unicode general necesita un contrato separado.

• ¿Devolvemos solo la distancia o un script de edición? Solo la distancia. Reconstruir las operaciones normalmente

retiene la tabla completa o información explícita de predecesores.

• ¿Puede alguna entrada estar vacía? Sí. Transformar una cadena vacía en un prefijo de longitud j necesita exactamente j

inserciones; lo inverso necesita i eliminaciones.

• ¿Cuáles son los límites de tamaño? Longitudes de hasta 2,000 hacen que un tiempo de O(mn) sea aceptable, pero hacen que la recursión

exponencial y la memoria innecesaria de tabla completa sean indeseables.

• ¿Se pueden intercambiar las entradas para ahorrar memoria? Sí, bajo este contrato de costo unitario porque la distancia es

simétrica. Menciona esa suposición antes de usarla.

Estructura de respuesta en 30 segundos

“Defino dp[i][j] como el mínimo de ediciones desde los primeros i caracteres de source hasta los primeros j caracteres de target. Los costos de prefijo vacío inicializan la primera fila y columna. Los caracteres finales iguales usan la diagonal sin cambios. De lo contrario, la última edición es eliminar, insertar o reemplazar, por lo que tomo uno más el mínimo de la celda superior, izquierda y diagonal. Cada celda depende solo de la fila anterior y del valor izquierdo de la fila actual, por lo que coloco la cadena más corta en las columnas y mantengo dos filas. Eso da un tiempo de O(mn) y un espacio de O(min(m, n)). Verifico cadenas vacías, cadenas iguales, longitudes asimétricas y el resultado contra una referencia de tabla completa en entradas pequeñas.”

Solución profunda paso a paso

Comienza a partir de prefijos. Sea dp[i][j] el número mínimo de ediciones permitidas que transforma source[0..i - 1] en target[0..j - 1].

Los límites de prefijo vacío se derivan directamente del contrato:

dp[0][j] = j   // insert all j target characters
dp[i][0] = i   // delete all i source characters

Para prefijos no vacíos, inspecciona sus caracteres finales. Si coinciden, mantener ese carácter final compartido reduce el problema a los dos prefijos más cortos:

if source[i - 1] == target[j - 1]:
  dp[i][j] = dp[i - 1][j - 1]

Si difieren, clasifica la edición final de cualquier secuencia óptima:

delete source[i - 1]:       dp[i - 1][j]     + 1
insert target[j - 1]:       dp[i][j - 1]     + 1
replace the final character: dp[i - 1][j - 1] + 1

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

Estos casos son exhaustivos porque la última operación debe ser una de las tres ediciones permitidas. Son constructivos: añade la edición nombrada a una solución óptima para el prefijo más pequeño seleccionado y produce una solución válida para (i, j). A la inversa, elimina la última edición de cualquier solución óptima; el resto resuelve el prefijo más pequeño correspondiente, por lo que no puede costar menos que esa celda. Esto demuestra la recurrencia para discrepancias.

Para caracteres finales coincidentes, existe una solución óptima que los deja emparejados. Si alguna secuencia óptima edita el carácter final de source o target, elimina esos efectos finales y alinea los caracteres iguales en su lugar; esto no incrementa el costo. El trabajo restante es exactamente el problema de prefijo diagonal. La inducción en i + j, anclada por los límites de prefijo vacío, demuestra cada celda y, por lo tanto, dp[m][n].

Solo se necesitan tres valores anteriores mientras se llena una fila: previous[j] para eliminación, current[j - 1] para inserción y previous[j - 1] para reemplazo o coincidencia. El código hace que la cadena más corta sea la de las columnas. Ese intercambio es una optimización de memoria bajo esta definición simétrica de costo unitario; no cambia la respuesta.

export function editDistance(source: string, target: string): number {
  const rows = source.length >= target.length ? source : target
  const columns = source.length >= target.length ? target : source

  let previous = Array.from(
    { length: columns.length + 1 },
    (_, index) => index,
  )

  for (let row = 1; row <= rows.length; row += 1) {
    const current = new Array<number>(columns.length + 1)
    current[0] = row

    for (let column = 1; column <= columns.length; column += 1) {
      if (rows[row - 1] === columns[column - 1]) {
        current[column] = previous[column - 1]
        continue
      }

      const deleteCost = previous[column] + 1
      const insertCost = current[column - 1] + 1
      const replaceCost = previous[column - 1] + 1
      current[column] = Math.min(deleteCost, insertCost, replaceCost)
    }

    previous = current
  }

  return previous[columns.length]
}

Para source = "horse" y target = "ros", la dimensión de columna más corta tiene longitud tres. La fila final termina en tres, coincidiendo con la secuencia de reemplazo más dos eliminaciones. El algoritmo devuelve el costo; no afirma que esta secuencia de edición en particular sea única.

Complejidad, límites y elecciones de ingeniería

El algoritmo llena (m + 1)(n + 1) estados conceptuales, por lo que el tiempo es O(mn). Cada fila tiene min(m, n) + 1 entradas y solo existen dos filas a la vez, por lo que el espacio auxiliar es O(min(m, n)). Reasignar una fila por iteración no cambia el límite; dos arreglos reutilizables pueden reducir la presión de asignación sin cambiar el algoritmo.

La respuesta máxima bajo inserción, eliminación y reemplazo unitarios es max(m, n): reemplazar los primeros min(m, n) caracteres y luego insertar o eliminar la diferencia de longitud. El mínimo es al menos |m - n|, porque cada edición cambia la longitud como máximo en uno. Estos límites son aserciones útiles en las pruebas.

Para cadenas generales de JavaScript, la indexación opera en unidades de código UTF-16. La iteración de cadenas preserva los pares suplentes al producir puntos de código Unicode, pero aún puede dividir un grupo de grafemas como un emoji más un tono de piel o una secuencia de unión de ancho cero (ZWJ). Una característica de similitud en producción debe decidir si las ediciones se aplican a unidades de código, puntos de código, grupos de grafemas normalizados, palabras o tokens de dominio antes de elegir un tokenizador. La normalización silenciosa también puede cambiar la semántica del producto, por lo que pertenece al contrato en lugar de estar dentro de este bucle de DP.

Si quien llama solo pregunta si la distancia es como máximo k, primero descarta cuando |m - n| > k, luego evalúa solo una banda diagonal y detén el proceso cuando ningún estado en la banda activa pueda permanecer dentro de k. Ese es un contrato de salida diferente; la implementación de distancia completa no debería agregar esa complejidad de forma especulativa.

Respuesta de muestra de alta calidad

“Modelaría el problema sobre prefijos. Sea dp[i][j] el costo mínimo para convertir los primeros i caracteres de source en los primeros j caracteres de target. Los límites de prefijo vacío son sus longitudes. Para caracteres finales iguales mantengo el valor diagonal. Para caracteres finales diferentes, clasifico una secuencia óptima por su última edición: eliminar usa la celda superior, insertar usa la celda a la izquierda y reemplazar usa la diagonal, sumando uno al mínimo. Esos casos son exhaustivos y eliminar la última edición demuestra la recurrencia en la otra dirección.

“Dado que una celda solo usa la fila anterior y la celda izquierda de la fila actual, mantengo dos filas. Los costos unitarios de inserción y eliminación hacen que esta distancia sea simétrica, por lo que la cadena más corta puede ser la de las columnas y la memoria pasa a ser O(min(m, n)); el tiempo se mantiene en O(mn). No usaría ese intercambio para pesos asimétricos. Probaría ambas direcciones vacías, cadenas iguales, el ejemplo de horse a ros y cadenas cortas generadas contra una versión de tabla completa. Si el entrevistador necesita el script de edición, retendría la información de predecesores en lugar de prometer recuperarla a partir de filas sobrescritas.”

Errores comunes

• Usar coincidencia voraz (greedy) de caracteres → caracteres repetidos y desplazamientos posteriores hacen que una edición localmente conveniente pierda

el mínimo global → definir estados de prefijo óptimos y comparar todas las operaciones finales válidas.

• Inicializar la primera fila y columna en cero → los casos de cadena vacía se vuelven gratuitos → **establecer los costos de límite

en sus longitudes de prefijo.**

• Confundir los vecinos de inserción y eliminación → el código puede pasar ejemplos simétricos fallando en prefijos

asimétricos → explicar qué cadena queda tras eliminar la operación final.

• Sumar uno cuando los caracteres finales coinciden → los caracteres iguales sin cambios se cobran como reemplazos → **copiar

la diagonal exactamente en caso de coincidencia.**

• Devolver una respuesta de filas rodantes mientras se promete un script de edición → los predecesores sobrescritos no pueden reconstruir

el camino → retener la matriz o punteros hacia atrás cuando se requieran las operaciones.

• Intercambiar cadenas bajo pesos asimétricos → las inserciones en una dirección se convierten en eliminaciones en la otra →

mantener la orientación original a menos que el modelo de costos sea simétrico.

• Llamar “caracteres” a los índices de JavaScript para Unicode arbitrario → los pares suplentes o grupos de grafemas se

cuentan de forma inesperada → definir y tokenizar la unidad de comparación explícitamente.

Un conjunto de pruebas enfocado incluye ("", "") = 0, ("", "abc") = 3, ("abc", "") = 3, ("same", "same") = 0, ("aaaa", "aa") = 2, ("horse", "ros") = 3 y ("intention", "execution") = 5. Compara la implementación rodante con una referencia de tabla completa sobre todas las cadenas cortas de un alfabeto pequeño. Comprueba también la identidad, la simetría bajo este modelo de costos, |m - n| ≤ d ≤ max(m, n) y la desigualdad triangular en tripletas generadas. Finalmente, ejecuta entradas iguales y completamente diferentes de longitud 2,000 para confirmar que la ruta de tamaño extremo se mantenga dentro del tiempo cuadrático y espacio lineal esperados.

Preguntas de seguimiento en entrevistas

Pregunta de seguimiento 1: ¿Cómo devolverías las operaciones de edición reales?

Conserva la tabla completa y realiza un rastreo inverso (backtracking) desde (m, n). Una coincidencia se mueve diagonalmente sin emitir una operación; de lo contrario, elige una celda vecina cuyo valor más el costo de edición correspondiente sea igual al valor actual. Define una regla de desempate estable porque pueden existir múltiples scripts mínimos. El método directo utiliza O(mn) de espacio. Una reconstrucción en espacio lineal es posible con técnicas de divide y vencerás, pero es un algoritmo separado y solo debe introducirse cuando el requisito de memoria lo exija.

Pregunta de seguimiento 2: ¿Qué cambia cuando las operaciones tienen pesos diferentes?

Agrega el peso relevante a cada transición en lugar de uno. La misma demostración de subestructura óptima funciona cuando los costos son no negativos y están definidos por el contrato. Si los costos de inserción y eliminación difieren, la distancia puede ser direccional, por lo que intercambiar las cadenas para acortar la fila ya no es automáticamente correcto. Los costos de edición negativos rompen la interpretación habitual y requieren reconsiderar el modelo.

Pregunta de seguimiento 3: ¿Cómo admitirías la transposición adyacente?

Primero aclara si una transposición solo intercambia caracteres adyacentes y si se permiten transposiciones superpuestas. Una recurrencia de alineación óptima de cadenas restringida puede inspeccionar dos caracteres precedentes adicionales y una celda dos filas y columnas hacia atrás. La distancia completa de Damerau–Levenshtein tiene requisitos de estado diferentes. Simplemente agregar una comprobación diagonal informal puede implementar la variante incorrecta.

Pregunta de seguimiento 4: ¿Cuál es la relación con la subsecuencia común más larga (LCS)?

Si el reemplazo está prohibido o cuesta lo mismo que una eliminación más una inserción, la distancia de inserción y eliminación se puede derivar de LCS como m + n - 2 * LCS(source, target). Con reemplazo de costo unitario, esa fórmula generalmente no es la distancia de edición: reemplazar un carácter discordante cuesta uno, mientras que eliminar más insertar cuesta dos. Especifica los costos de las operaciones antes de utilizar la relación.

Pregunta de seguimiento 5: ¿Cómo responderías más rápido a “¿es la distancia como máximo k?”?

Devuelve falso inmediatamente cuando la diferencia de longitud exceda k. De lo contrario, calcula solo los estados dentro de k respecto a la diagonal principal, tratando las celdas fuera de la banda como inalcanzables, y detén el cálculo si la frontera activa no puede volver a estar dentro del presupuesto. Esto puede reducir el trabajo sustancialmente cuando k es pequeño, mientras que el peor caso para la distancia sin restricciones sigue siendo cuadrático.

Pregunta de seguimiento 6: ¿Cómo manejarías texto Unicode visible para el usuario real?

Elige la unidad con el responsable del producto. La iteración por puntos de código evita dividir pares suplentes, pero todavía divide algunos caracteres percibidos por el usuario. La segmentación por grafemas coincide mejor con los caracteres visibles y la normalización Unicode puede hacer que secuencias canónicamente equivalentes se comparen de manera consistente. La configuración regional (locale), el case folding, los acentos y las reglas a nivel de tokens son decisiones de producto. Aplica ese preprocesamiento antes de la DP y prueba ejemplos de los lenguajes soportados.

Pregunta de seguimiento 7: ¿Puede una sola fila reemplazar a dos filas?

Sí. Antes de sobrescribir dp[j], guarda su valor anterior como la siguiente diagonal; dp[j] todavía representa la celda superior, y dp[j - 1] ya representa la celda izquierda de la fila actual. Esto reduce el factor constante, no el espacio asintótico. En una entrevista, dos filas suelen ser más fáciles de demostrar y menos propensas a errores a menos que el entrevistador solicite específicamente la variante in-place.