Longest Common Subsequence (LCS)
H · hardPracticestringsdp
Problem
Given two strings, find the length of their Longest Common Subsequence (LCS).
Example
Input
ABCBDAB BDCABA
Output
4
dp[i][j] = LCS of s1[:i] and s2[:j]. If chars match: dp[i][j]=dp[i-1][j-1]+1, else max(left, up).
LCS = BCBA (length 4)