DP 26. Print Longest Common Subsequence | DP on Strings

In previous lectures, we learned how to find the length of the Longest Common Subsequence (LCS) using memoization, tabulation, and space optimization. However, knowing the length is often only half the battle. In this chapter, we extend our dynamic programming foundation to reconstruct and print the actual string of the Longest Common Subsequence using our completed 2D tabulation table.

1. Why Do We Need to Print the Subsequence?

• Beyond Length: Finding that the LCS length is 3 between two strings ("abcde" and "bdgek") tells us how many characters are common, but it does not tell us which characters they are.
• String Reconstruction: Real-world applications (such as diff tools, DNA sequence alignment, and version control systems) require displaying the actual sequence of matching elements, not just a numerical count.
• The Challenge: While memoized or space-optimized tables throw away historical state data to save memory, a full 2D tabulation DP table retains the complete history of subproblems, allowing us to backtrack from the end to the beginning and reconstruct the sequence.

2. Core Mental Model: Backtracking Through the DP Table

Real-Life Analogy

Imagine walking through a mountain range where each cell in our 2D grid represents an elevation checkpoint. The bottom-right corner (dp[n][m]) represents the peak, holding the maximum length of our common subsequence for the entire strings. To find the path we took to reach this peak, we start at the summit and trace our steps backward down the mountain, following the exact rules by which the elevation numbers were generated until we reach the base.

3. Understanding the 1-Based Indexing and DP Table Layout

Let us consider two strings with 1-based indexing:

• s1 = "abcde" (Length $n = 5$, indices $1$ to $5$)
• s2 = "bdgek" (Length $m = 5$, indices $1$ to $5$)

The resulting 2D DP table stores the length of the LCS for prefixes of s1 and s2. For example:

• dp[5][5] = 3 signifies that for the entire string "abcde" (length 5) and "bdgek" (length 5), the longest common subsequence length is 3.
• dp[4][2] = 2 signifies that for "abcd" (length 4) and "bd" (length 2), the longest common subsequence length is 2.

4. The Backtracking Decision Rules

When we are standing at cell (i, j) in our populated DP table, we inspect the characters at s1[i - 1] and s2[j - 1] and evaluate two core conditions:

Case A: Characters Match (s1[i - 1] == s2[j - 1])

• Action: The character is part of our LCS. We store s1[i - 1] into our result string.
• Movement: We move diagonally backward to (i - 1, j - 1) because this value was derived by adding 1 to the subproblem of both prefixes shortened by 1.

Case B: Characters Do NOT Match (s1[i - 1] != s2[j - 1])

• Action: The current characters do not contribute to a shared subsequence extension. The value in dp[i][j] must have come from taking the maximum of either the cell above it (dp[i - 1][j]) or the cell to its left (dp[i][j - 1]).
• Movement: We inspect which neighbor is larger and move our pointer toward that larger value:
  • If dp[i - 1][j] > dp[i][j - 1], move up: i = i - 1.
  • Else, move left: j = j - 1. (Note: If both values are equal, we can move in either direction, though it may represent alternate valid LCS paths).

5. Step-by-Step Backtracking Walkthrough

Let's trace our backtracking algorithm on our sample strings:

• s1 = "abcde"
• s2 = "bdgek"
• Target LCS Length = 3

We allocate a result string (or character array) of length 3 initialized with placeholder characters, and an index pointer starting at length - 1 (2).

1. At (i = 5, j = 5):
   • s1[4] == 'e', s2[4] == 'k'. They do not match.
   • Look at neighbors: dp[4][5] vs dp[5][4]. The value comes from the top/left max. We move to the max cell.
2. Moving through non-matching cells: We shift pointers upwards or leftwards until we land on a matching pair.
3. At a Match ('e' and 'e'):
   • Characters match!
   • Store 'e' at our current result index (2).
   • Decrement result index to 1.
   • Move diagonally: i = i - 1, j = j - 1.
4. Continuing the Loop: We repeat this process until either i == 0 or j == 0. We encounter matches for 'd' and 'b', successfully reconstructing the string "bde".

6. Complete Implementation Code

Below is the complete C++ implementation demonstrating how to build the 2D tabulation table and backtrack to print the Longest Common Subsequence:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string findLCS(string s1, string s2) {
    int n = s1.length();
    int m = s2.length();

    // Step 1: Create and populate the 2D DP tabulation table
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Step 2: Backtrack from dp[n][m] to reconstruct the LCS string
    int len = dp[n][m];
    int i = n, j = m;

    // Create a string of length 'len' filled with dummy characters
    string lcs(len, '$');
    int index = len - 1;

    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs[index] = s1[i - 1];
            index--;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

int main() {
    string s1 = "abcde";
    string s2 = "bdgek";

    string result = findLCS(s1, s2);
    cout << "The Longest Common Subsequence is: " << result << endl;

    return 0;
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Tabulation is Mandatory for Backtracking: Space-optimized 1D array solutions discard row history, making it impossible to backtrack. A full 2D DP table must be maintained to print the string.
• Summit to Base Strategy: Reconstruction begins at the bottom-right corner (dp[n][m]) and terminates when either string index reaches 0.
• Match Condition (Diagonal Move): When characters match (s1[i - 1] == s2[j - 1]), record the character into the result string and move diagonally (i - 1, j - 1).
• Mismatch Condition (Greedy Max Move): When characters do not match, move toward the larger adjacent cell (dp[i - 1][j] or dp[i][j - 1]).
• Multiple Optimal Paths: If adjacent cells have equal maximum values, multiple valid LCS strings may exist; standard backtracking picks one deterministic path.
• Linear Backtracking Cost: Tracing back through the grid takes at most $O(N + M)$ time in the worst-case path traversal.