Longest Common Subsequence Problem (LCS)

The Longest Common Subsequence (LCS) problem is a classic Dynamic Programming problem. It involves finding the longest sequence which appears in both given sequences (not necessarily contiguous).

Approach:

1. Input: Two sequences $A[\mathrm{1..}n]$ and $B[\mathrm{1..}m]$ of characters.
2. Output: The maximum length $k$ of a common subsequence between $A$ and $B$.
3. Example: For example, if $A=$ “blurry” and $B=$ “burger”, the longest common subsequence is “burr”.
4. Idea: The LCS problem can be solved using dynamic programming, typically using a two-dimensional array to store the lengths of the LCS of prefixes of the sequences.
5. Recurrence: At each cell $(i,j)$ of the 2D array (where $i$ represents the index of $A$ and $j$ represents the index of $B$), you consider three cases:
   • If $A[i]\ne B[j]$, then the LCS does not include either $A[i]$ or $B[j]$, so the length of the LCS up to that point remains the same as it was without including these characters. You can look at the cell $(i-1,j)$ or $(i,j-1)$ to find the length of the LCS.
   • If $A[i]=B[j]$, then you can extend the LCS by one. In this case, the length of the LCS would be one plus the length of the LCS up to the previous characters, i.e., $(i-1,j-1)+1$.
   • You take the maximum of these two options.
6. Adding 1 in the diagonal arrow: When characters match (case 3), we add one to the LCS length because we’re extending the LCS by one character. However, in cases where characters don’t match (cases 1 and 2), we don’t add anything because the current characters don’t contribute to the LCS. So, we don’t add one in those cases.
7. Finding the Solution: Once the dynamic programming table is filled, the solution lies in the bottom-right cell of the table, which represents the LCS length.
8. Complexity: The time complexity of this approach is $O(n\cdot m)$, where $n$ and $m$ are the lengths of sequences $A$ and $B$ respectively. This is because you fill a 2D array of size $n\times m$.