LCS Subsequence
AlgorithmsMediumFind the longest subsequence shared across two string configurations.
Alt+Shift+L
Configuration Panel
LCS DP Grid (backtrack path highlighted)
DP table is empty.
Time Complexity
O(N * M)
Space Complexity
O(N * M) table space
Conceptual Overview
The Longest Common Subsequence (LCS) problem finds the longest subsequence common to all sequences in a set of sequences (subsequences do not need to occupy consecutive positions).
Recurrence Relation
dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1] else max(dp[i-1][j], dp[i][j-1])
State Transitions
Decides to match characters (increment diagonal) or skip characters (taking maximum of top or left cell).
Source: CP-Algorithms dynamic programming reference