Longest Common Subsequence
Given two strings, return the length of the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguously).
- 1 ≤ text1.length, text2.length ≤ 1000
- Lowercase English letters
- Two sequences, subsequence alignment
- State = prefix of each string → 2D table
- Matching last characters extends the diagonal; otherwise drop one character
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Define L[i][j] as the LCS length of the first i characters of one string and the first j of the other. If the two characters at those ends match, L[i][j] = L[i-1][j-1] + 1; otherwise it is max(L[i-1][j], L[i][j-1]). Fill the table row by row starting from zeros; L[m][n] is the answer. Only the previous row is needed for the length alone.
- Recovering the actual subsequence requires the full table and a backtrack. Bit-parallel algorithms speed up long strings by a word-size factor.