# Solution: Longest Common Subsequence of Two Sequences

Solution for the Longest Common Subsequence of Two Sequences Problem.

We'll cover the following

## Solution

Consider a longest common subsequence $C = (c_1 , \ldots, c_p )$ specified by indices $1≤i_1 and $1≤j_1 (therefore, for every $1≤q≤p, a_{i_{q}}=b_{j_{q}} =c_q$).

• Last symbols of $A$ and $B$ appear in $C$. In this case, $i_ p =n$ and $j_p =m$. Then, $(c_1,\ldots,c_{p−1})$ is a longest common subsequence of $(a_1,\ldots,a_{n−1})$ and $(b_1,\ldots,b_{m−1})$.

• At least one of the last symbols of $A$ and $B$ doesn’t appear in $C$. In this case, either $i_p < n$ or $j_p < m$. Then, $(c_1,\ldots,c_{p−1})$ lies entirely in either $(a_1,\ldots,a_{n−1})$ or $(b_1,\ldots,b_{m−1})$.

This way, we reduce the problem for the initial strings $A$ and $B$ to the same problem on their prefixes. This motivates the following definition: $LCS(i,j)$ is the length of the longest common subsequence of $A[1\ldots i]$ and $B[1\ldots j]$. The discussion above implies that this function satisfies the following recurrence relation:

$LCS(i , j) = \text{max} \begin{cases} LCS(i-1 , j) \\ LCS(i , j-1) \\ LCS(i-1 , j-1)+1 & \text{if }~~ A[i]=B[j] \end{cases}$

The base case for this recurrence relation is $i = 0$ or $j = 0$:

$LCS(0,j) = LCS(i,0) = 0.$

The resulting algorithm is shown below. Its running time is $O(nm)$.

$LCS(A[1\ldots n],B[1 \ldots m])$:
$table ←$ 2d array of size $(n + 1) × (m + 1)$
$table[i][0] ← 0$ and $table[0][j] ← 0$ for all $i,j$
for all $i,j$ for $i$ from $1$ to $n$:
for $j$ from $1$ to $m$:
$table[i][j] ← table[i − 1][j]$
$table[i][j] ← max(table[i][j], table[i][j − 1])$
if $A[i] = B[j]$:
$table[i][j] ← max(table[i][j], table[i − 1][j − 1] + 1)$
return $table[n][m]$

Stop and think: Can you reduce the Longest Common Subsequence Problem to the Edit Distance Problem?

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.