Overview
La Subsecuencia Común Más Larga (LCS) encuentra la subsecuencia más larga presente en ambas cadenas (los caracteres no necesitan ser contiguos).
Analogy
Como encontrar el guión común de dos canciones — buscas las palabras que aparecen en el mismo orden en ambas, aunque no de forma consecutiva.
Step-by-step
- Crea tabla DP: dp[i][j] = longitud de LCS de s1[:i] y s2[:j]
- Si s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- Sino: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- dp[m][n] es la longitud de LCS
Visual
"ABCBDAB" y "BDCAB"
LCS = "BCAB" o "BDAB" (longitud 4)
Common mistakes
- Confundir LCS con substring común más largo (debe ser contiguo)
- No rastrear la subsecuencia real (solo su longitud)
Practice questions
- Reconstruye la LCS real rastreando hacia atrás la tabla DP
- Usa LCS para implementar diff (líneas añadidas/eliminadas)
Time
O(m×n) — m y n son las longitudes de las cadenas
Space
O(m×n) → optimizable a O(min(m,n))