Longest Common Subsequence (LCS)?

int LCS(string s1, string s2)

int m = s1.Length, n = s2.Length;

int[,] dp = new int[m + 1, n + 1];

for (int i = 1; i <= m; i++)

for (int j = 1; j <= n; j++)

if (s1[i - 1] == s2[j - 1])

dp[i, j] = dp[i - 1, j - 1] + 1;

else

dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);

return dp[m, n];

Explanation:

Build DP table comparing chars; find longest subsequence common to both strings.

Follow on: