Visualize the Longest Common Subsequence algorithm filling a 2D DP table character-by-character, then watch the backtrack reveal the actual shared subsequence.
Find the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous). A fundamental DP problem used in diff tools, bioinformatics, and version control.
Given two strings s1 and s2, find the longest subsequence present in both. A subsequence keeps the original order but can skip characters. For example: s1 = "SUNDAY", s2 = "SATURDAY" → LCS = "SDAY" (length 4).
Create a (m+1) × (n+1) table where dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1]. Row 0 and column 0 are all zeros (LCS with an empty string is 0). Fill the table row by row, left to right.
For each cell dp[i][j]: if s1[i-1] === s2[j-1] (characters match) → dp[i][j] = dp[i-1][j-1] + 1 (extend the diagonal). Otherwise → dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the best of skipping either character).
Start at dp[m][n] and work backwards. If s1[i-1] === s2[j-1], prepend that character to the result and move diagonally (i--, j--). Otherwise, move to the larger neighbor: if dp[i-1][j] ≥ dp[i][j-1] go up, else go left.
LCS is the backbone of diff utilities (git diff, patch), DNA sequence alignment in bioinformatics, and spell-checkers. The space complexity can be reduced to O(min(m,n)) with a rolling two-row approach, though the full table is needed to reconstruct the sequence.