🔤 Longest Common Subsequence

Problem

Find the longest sequence that appears in both strings in the same order (not necessarily contiguous).

Recurrence:

If $X[i] = Y[j]$: $dp[i][j] = 1 + dp[i-1][j-1]$

Else: $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$