Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Dynamic Programming Visualizer

Longest Common Subsequence

Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Table Size 0×0
Cells Filled 0
Status Ready
Uncomputed
Filling
Optimal path
0 / base case
Step Explanation

Select an algorithm and press Play to watch the table fill in.

—
Pseudocode 
 
 
 
 
  
 
 
Longest Common Subsequence (LCS)
  
 
  Intermediate (3/5)
 
~1 hora   Subsecuencia común más larga  DP 2D: match vs skip  Reconstrucción de la secuencia  Relación con edit distance  
Prereqs: Programación dinámica, Subsecuencias vs substrings  
 
Quick Reference
Longest Common Subsequence
The Longest Common Subsequence problem finds the longest sequence of characters that appears in the same order in two strings (but not necessarily contiguously). Used in diff tools, bioinformatics, and version control.

Difficulty: Intermediate (3/5)
dp
Complexity
Best Time
O(mn)
Average Time
O(mn)
Worst Time
O(mn)
Space
O(mn)
When to Use
For comparing sequences: file diffs, DNA/protein alignment, plagiarism detection, and edit-distance related problems.
Pros
  • Exact solution with clear DP formulation
  • Widely applicable to sequence comparison
  • O(mn) time is optimal for general strings
Cons
  • O(mn) space for reconstruction
  • Slow for very long strings
  • Returns length unless reconstructed carefully
History
The LCS problem was first studied in the 1970s and is a classic application of dynamic programming, appearing in the landmark 1974 paper by Hirschberg on optimal sequence alignment.
 
 
Longest Common Subsequence (LCS) encuentra la subsecuencia más larga que aparece en el mismo orden relativo en dos secuencias. A diferencia de substring, los caracteres no necesitan ser contiguos — solo preservar el orden.


Es uno de los problemas DP más icónicos, con aplicaciones en diff de texto, bioinformática (alineamiento de ADN), y como base para edit distance.


Cómo Funciona


    

  1. Inicializa tabla DP dp[i][j] = longitud LCS de A[0..i) y B[0..j).
    2. 

  2. Recurre:

      

    • “Si A[i-1] == B[j-1]: dp[i][j] = 1 + dp[i-1][j-1] (match)”
      • 

    • “Si no: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip)”
      • 

    

    3. 

  3. Resultado: dp[m][n]
    4. 

  4. Reconstruye: backtrack desde dp[m][n] para obtener la secuencia actual.
    5. 



Idea Clave


LCS es un ejercicio de match o skip: en cada posición (i,j), o los caracteres coinciden y los usas, o no coinciden y debes saltar uno de ellos. La tabla 2D captura todas las combinaciones de prefijos.


La reconstrucción requiere backtrack: desde dp[m][n], si A[i-1] == B[j-1] ese carácter está en el LCS; si no, sigue la dirección del máximo.


Ejemplo Trabajado


A = "ABCBDAB", B = "BDCABA"


Tabla DP (longitudes):


      Ø  B  D  C  A  B  A
Ø [ 0, 0, 0, 0, 0, 0, 0 ]
A [ 0, 0, 0, 0, 1, 1, 1 ]
B [ 0, 1, 1, 1, 1, 2, 2 ]
C [ 0, 1, 1, 2, 2, 2, 2 ]
B [ 0, 1, 1, 2, 2, 3, 3 ]
D [ 0, 1, 2, 2, 2, 3, 3 ]
A [ 0, 1, 2, 2, 3, 3, 4 ]
B [ 0, 1, 2, 2, 3, 4, 4 ]


Resultado: dp[7][6] = 4. LCS = "BCBA" o "BDAB" (empate).


Casos Extremos y Trampas


    

  • Sin caracteres comunes — LCS = 0.
    • 

  • Secuencias idénticas — LCS = longitud completa.
    • 

  • Espacio — se puede reducir a O(min(m,n)) si solo necesitas la longitud, no la secuencia.
    • 

  • Reconstrucción — requiere la tabla completa o clever on-the-fly.
    • 



Comparación con Variantes































ProblemaMatchComplejidadUso
LCSNo contiguoO(mn)Diff, bioinformática
LCSubstrContiguoO(mn)Plagio detección
Edit DistanceIns/del/replaceO(mn)diff, spell check


Aplicaciones


    

  • Diff de texto — git diff, Word track changes
    • 

  • Bioinformática — alineamiento de ADN/ARN (Needleman-Wunsch)
    • 

  • Sistemas de control de versiones — merge de cambios
    • 

  • Enseñanza — ejemplo clásico de DP 2D con backtracking
    • 



Trayectoria de Práctica


    

  1. Implementa LCS con tabla 2D; traza A="ABCBDAB", B="BDCABA".
    2. 

  2. Añade backtracking para reconstruir la secuencia actual.
    3. 

  3. Modifica para retornar la longitud solo, usando O(min(m,n)) espacio.
    4. 

  4. Compara con longest common substring: ¿por qué la recurrencia cambia?
    5. 

  5. Extiende a edit distance (Levenshtein): añade operación de replace.
    6.