Longest Common Subsequence Using Dynamic Programming

Longest Common Subsequence Using Dynamic Programming

The longest common subsequence (LCS) problem is a classic challenge in computer science that asks for the longest sequence of characters that appears in the same relative order (but not necessarily contiguously) in two given strings. Solving it efficiently is essential for applications ranging from bio‑informatics (DNA sequence alignment) to version‑control systems (diff tools) and natural‑language processing. Still, the most widely taught and practically useful solution employs dynamic programming, a technique that breaks the problem into overlapping subproblems, stores intermediate results, and builds up the final answer in polynomial time. This article walks through the concept, the algorithm, its implementation details, and practical considerations, giving you a solid foundation to apply LCS in real‑world projects Small thing, real impact..

Understanding the Longest Common Subsequence

Before diving into the algorithm, it helps to clarify what a subsequence is. A subsequence of a string is any sequence that can be derived by deleting zero or more characters without changing the order of the remaining characters. To give you an idea, “abc”, “ac”, and “bc” are all subsequences of “abc”, while “ca” is not because it reverses the order.

The longest common subsequence of two strings X and Y is the longest string Z that is a subsequence of both X and Y. If multiple subsequences share the maximum length, any one of them is a valid answer.

Example:
X = “ABCBDAB”
Y = “BDCABA”

One LCS is “BCBA” (length 4). Another equally long LCS is “BDAB”. Both are acceptable.

The naive approach—checking every subsequence of X against Y—has exponential time complexity because a string of length n has 2ⁿ possible subsequences. Dynamic programming reduces this to O(m·n), where m and n are the lengths of the two strings Most people skip this — try not to. Worth knowing..

Dynamic Programming Approach: Core Idea

Dynamic programming solves LCS by constructing a table dp where each entry dp[i][j] stores the length of the LCS of the prefixes X[0…i‑1] and Y[0…j‑1]. The table is filled iteratively using the following recurrence:

• If X[i‑1] == Y[j‑1], then the characters match and can be part of the LCS:
  dp[i][j] = dp[i‑1][j‑1] + 1
• Otherwise, the best LCS length comes from either dropping the current character of X or dropping the current character of Y:
  dp[i][j] = max(dp[i‑1][j], dp[i][j‑1])

The base case is dp[0][] = dp[][0] = 0, representing an empty prefix.

After filling the table, dp[m][n] holds the length of the LCS. To retrieve the actual subsequence, we backtrack from dp[m][n] to dp[0][0], following the decisions that led to each cell.

Step‑by‑Step Algorithm

Below is a detailed breakdown of the LCS‑DP algorithm, suitable for implementation in languages like Python, Java, C++, or JavaScript.

1. Input: Two strings X (length m) and Y (length n).
2. Initialize: Create a (m+1) × (n+1) integer matrix dp, filled with zeros.
3. Fill the table:
   • For i from 1 to m:
     • For j from 1 to n:
       • If X[i‑1] == Y[j‑1]: dp[i][j] = dp[i‑1][j‑1] + 1
       • Else: dp[i][j] = max(dp[i‑1][j], dp[i][j‑1])
4. Length of LCS: The value dp[m][n] is the answer’s length.
5. Reconstruct the LCS (optional):
   • Set i = m, j = n, and create an empty list lcs_rev.
   • While i > 0 and j > 0:
     • If X[i‑1] == Y[j‑1]: prepend X[i‑1] to lcs_rev; decrement i and j.
     • Else if dp[i‑1][j] ≥ dp[i][j‑1]: decrement i.
     • Else: decrement j.
   • Reverse lcs_rev to obtain the LCS in correct order.

Pseudocode

function LCS(X, Y):
    m ← length(X)
    n ← length(Y)
    dp ← (m+1) × (n+1) matrix initialized to 0

    for i from 1 to m:
        for j from 1 to n:
            if X[i-1] == Y[j-1]:
                dp[i][j] ← dp[i-1][j-1] + 1
            else:
                dp[i][j] ← max(dp[i-1][j], dp[i][j-1])

    // Length of LCS
    lcs_len ← dp[m][n]

    // Reconstruct one LCS (optional)
    i ← m; j ← n
    lcs_rev ← empty list
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            prepend X[i-1] to lcs_rev
            i ← i - 1; j ← j - 1
        else if dp[i-1][j] ≥ dp[i][j-1]:
            i ← i - 1
        else:
            j ← j - 1

People argue about this. Here's where I land on it.

    lcs ← reverse(lcs_rev)
    return (lcs_len, lcs)

Complexity Analysis

And yeah — that's actually more nuanced than it sounds.

The quadratic time is optimal for the general case unless additional constraints (e.g., bounded alphabet size) allow faster algorithms like the Hunt‑Szymanski method Which is the point..

Worked Example

Let’s trace the algorithm on X = “ABCBDAB” (m = 7) and Y = “BDCABA” (n = 6) Small thing, real impact..

1. Initialize dp (8 × 7 zero matrix).
2. Fill (showing only a few steps for brevity):

Completing the Worked Example

Below is the fully populated DP matrix for the two input strings

X = “ABCBDAB”   (m = 7)
Y = “BDCABA”    (n = 6)

Bold entries mark a match (X[i‑1] == Y[j‑1]); all other cells hold the larger of the left‑ or upper‑neighbor.

The bottom‑right cell dp[7][6] equals 5, which is the length of a longest common subsequence. One concrete LCS obtained by back‑tracking is:

X: A B C B D A B
Y: B D C A B A
          ↑
LCS: B A B A   (positions: X[2], X[6], X[7]; Y[1], Y[5], Y[6])

The reconstruction walk looks like this (coordinates refer to the DP table):