DP: Longest Common Subsequence (LCS) – Examples and Exercises

In this lesson, we introduce the Longest Common Subsequence (LCS) problem, a classic example in dynamic programming. You will learn how to define the DP state, construct the DP table, and analyze the resulting solution step by step.

Problem Statement — Longest Common Subsequence (LCS)

Two strings X and Y are given. The task is to determine the length of the longest common subsequence (Longest Common Subsequence — LCS) between these two strings.

A subsequence does not have to be contiguous — characters may be selected from arbitrary positions, but their relative order must be preserved.

Input

• The first line contains the string X
• The second line contains the string Y

Output

• Print a single integer — the length of the longest common subsequence

Example

Input:
AGGTAB
GXTXAYB

Output:
4

Explanation:
One of the longest common subsequences is "GTAB".

Note

• If there is no common character, the result is 0.
• The task requires only the length of the LCS, not the subsequence itself.

Visual Interpretation of the DP Table (LCS)

One of the most common difficulties when understanding the LCS algorithm is how the DP table is filled and why, in certain cases, we take the maximum value from neighboring cells.

Let us consider the following example:

X = "AGGTAB"
Y = "GXTXAYB"

We construct a DP table of dimensions (|X|+1) × (|Y|+1), where dp[i][j] represents the length of the LCS of the prefixes X[0..i-1] and Y[0..j-1].

Initial DP Table

      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0
   G  0
   G  0
   T  0
   A  0
   B  0
  

The first row and the first column contain zeros, because the LCS with an empty string always has length 0.

How Is a Single Cell Computed?

Let us examine the cell dp[i][j]:

• If the characters are equal:
  X[i-1] == Y[j-1]
  then:

  dp[i][j] = dp[i-1][j-1] + 1

  ➜ We move diagonally, since we have extended a common subsequence.

• If the characters are not equal:

  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  ➜ We choose the better of two options:

  • skip a character from string X (top)
  • skip a character from string Y (left)

Example of a Filled DP Table

      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0  0  0  0  0  1  1  1
   G  0  1  1  1  1  1  1  1
   G  0  1  1  1  1  1  1  1
   T  0  1  1  2  2  2  2  2
   A  0  1  1  2  2  3  3  3
   B  0  1  1  2  2  3  3  4
  

The value in the bottom-right corner dp[|X|][|Y|] represents the length of the longest common subsequence. In this example, it is 4.

Why Do We Take the Maximum from the Top and Left?

When the characters do not match, the current character cannot be part of a common subsequence. Therefore, we examine two possibilities:

• ignore the character from the first string (top)
• ignore the character from the second string (left)

We choose the option that yields a longer common subsequence, since the goal is to maximize the LCS length.

Problem Description

Two sequences or strings X[1..n] and Y[1..m] are given. The goal is to find the longest subsequence that appears in both sequences. The subsequence does not have to be contiguous.

Example:

X = "AGGTAB"
Y = "GXTXAYB"
Longest common subsequence: "GTAB", length = 4
  

Definition of the DP State

Let dp[i][j] represent the length of the LCS of the first i characters of string X and the first j characters of string Y.

Transitions:

• If the last characters are equal: dp[i][j] = dp[i-1][j-1] + 1
• If they are not equal: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases:

• dp[0][j] = 0 for all j
• dp[i][0] = 0 for all i

Detailed Explanation of the Longest Common Subsequence (LCS) Problem

The Longest Common Subsequence (LCS) problem is one of the most important and common examples of dynamic programming. Given two sequences (often strings), the goal is to find the longest subsequence that appears in both sequences while preserving the same order of elements, but without requiring them to be consecutive.

What is LCS?

For example, given the sequences X = "ABCBDAB" and Y = "BDCABA", one of the longest common subsequences is BCBA, of length 4. It is important that the elements of the LCS appear in the same order in both sequences, but there may be skipped characters in between.

Why is the naive solution inefficient?

A naive approach would try to generate all subsequences of X (there are 2ⁿ of them), check which ones appear in Y, and find the longest. However, the number of subsequences grows exponentially — for a string of 30 characters, there are over a billion subsequences. In practice, this is infeasible, so a more efficient method is required.

Why do we use dynamic programming?

The key idea is that the LCS problem can be divided into smaller subproblems. The length of the LCS for prefixes X[1…i] and Y[1…j] depends only on the LCS of their smaller prefixes. This is why we construct a DP matrix, where each element represents the result of a subproblem that is later used to build the final solution.

Definition of the DP State

Let dp[i][j] represent the length of the LCS of the first i characters of string X and the first j characters of string Y. The dp matrix is filled from smaller to larger prefixes.

Base Cases

dp[0][j] = 0  (an empty sequence has no common subsequence)
dp[i][0] = 0
    

Logic for Filling the DP Matrix

1) If the last characters match

If X[i] == Y[j], then this character must be part of the LCS. The transition is:

dp[i][j] = dp[i-1][j-1] + 1
    

2) If the last characters do not match

If X[i] ≠ Y[j], then this character cannot be part of the LCS. Therefore, we choose the better of two possible options:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

This means: either we discard the last character of X, or the last character of Y, and take the best solution from these two subproblems.

What does the DP matrix look like in practice?

For sequences of length m and n, we create a table of size (m+1) × (n+1). The first row and the first column are zeros. Each cell is filled using the rules above. At the end, dp[m][n] contains the length of the longest common subsequence.

Why is this efficient?

The DP approach runs in O(m × n) time, which is a huge improvement over the exponential naive approach. For example, for two strings of 1000 characters, DP performs around a million operations — easily manageable in modern computing time.

Summary of the DP Solution

State:        dp[i][j] = LCS(X[1..i], Y[1..j])
Base:         dp[0][*] = dp[*][0] = 0
Match:        dp[i][j] = dp[i-1][j-1] + 1
Mismatch:     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

This is the most classic example of dynamic programming and prepares students for many other advanced algorithms that use the same principle of breaking a problem into smaller overlapping subproblems.

Example of Filling the DP Matrix for LCS

Let's take a concrete example: X = "ABCBDAB", Y = "BDCABA". The matrix below shows how the DP table is filled step by step. Rows correspond to characters of X, and columns correspond to characters of Y.

The final result is located in the bottom-right corner of the matrix: dp[7][6] = 4, meaning that the length of the LCS is 4.

Pseudocode for the LCS Algorithm

function LCS(X, Y):

    # Take the lengths of both strings
    m = length(X)
    n = length(Y)

    # Create a DP matrix where dp[i][j] represents
    # the length of the LCS for the first i characters of X and first j characters of Y.
    # The matrix has (m+1) rows and (n+1) columns to handle cases when
    # one of the strings is empty.
    create matrix dp of size (m+1) × (n+1)

    # Initialize the DP base cases:
    # If either string has length 0, LCS is always 0.
    for i = 0..m:
        dp[i][0] = 0  # LCS with empty Y
    for j = 0..n:
        dp[0][j] = 0  # LCS with empty X

    # Fill the DP matrix row by row, column by column
    for i = 1..m:
        for j = 1..n:

            # If the current characters match,
            # they are part of the LCS. Add 1 to the solution
            # of the previous prefixes (i-1, j-1).
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # Include this character in LCS

            # If the characters do not match, the best LCS
            # is obtained by either removing:
            #  - the last character from X  (dp[i-1][j])
            #  - the last character from Y  (dp[i][j-1])
            # Take the maximum of these two options.
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Exclude one character

    # Final result — length of the LCS — is located
    # in the bottom-right corner of the matrix.
    return dp[m][n]  # LCS length

Python Implementation

def lcs(X, Y):
    m = len(X)  # Length of string X
    n = len(Y)  # Length of string Y

    # Create DP matrix with extra row and column for empty prefixes
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill the DP matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):

            # Characters match → extend previous LCS by 1
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            # Characters do not match → take maximum of excluding one character
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Return the length of LCS
    return dp[m][n]

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lcs(string X, string Y) {
    int m = X.size(); // Length of X
    int n = Y.size(); // Length of Y

    // Create DP matrix initialized with 0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Fill the DP matrix
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {

            // Characters match → extend previous LCS
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            // Characters do not match → take maximum from left or top
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // Bottom-right cell contains the final LCS length
    return dp[m][n];
}

Tabulation and Solution Analysis

The DP table is filled in order (bottom-up). At the end, dp[n][m] contains the length of the longest common subsequence.

// DP: Longest Common Subsequence (LCS)
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    // Given strings
    string X = "AGGTAB";
    string Y = "GXTXAYB";

    // n and m are their lengths
    int n = X.size();
    int m = Y.size();

    // DP table of size (n+1) × (m+1)
    // dp[i][j] represents the length of the LCS between
    // the first i characters of X and the first j characters of Y.
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    // Fill the DP matrix — bottom-up approach.
    // Start from (1,1) because the first row and column are already 0
    // (base case: comparing with empty string → LCS = 0).
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {

            // If characters match — they are part of the LCS
            // so we add 1 to the result of previous prefixes.
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;

            // If they do not match — take the best result
            // between:
            // 1) removing the last character from X → dp[i-1][j]
            // 2) removing the last character from Y → dp[i][j-1]
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // LCS length is in the bottom-right corner of the DP table
    cout << "LCS length: " << dp[n][m] << endl;

    // ----------------------------------------------
    //  Optional: Reconstruction of the actual LCS.
    //  Start from dp[n][m] and trace back through the DP table.
    // ----------------------------------------------

    string lcs = "";
    int i = n, j = m;

    // While we have not reached the first row or column
    while(i > 0 && j > 0) {

        // If characters match — they are part of the LCS.
        // Add them to the beginning of the result.
        if(X[i-1] == Y[j-1]) {
            lcs = X[i-1] + lcs;
            i--;
            j--;
        }

        // If they do not match, move in the direction
        // of the larger value in the DP table.
        else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    // Print the reconstructed LCS sequence
    cout << "LCS: " << lcs << endl;

    return 0;
}
  

Analysis:
– Time complexity: O(n*m)
– Memory: O(n*m) (can be optimized to O(min(n,m)) by using only two rows)
– The example also demonstrates reconstruction of the subsequence.

Additional Example: Longest Common Subsequence

Let's consider a new example to practice LCS calculation:

X = "XMJYAUZ"
Y = "MZJAWXU"

Longest Common Subsequence: "MJAU"
  

Step by step, we can fill the DP table and trace the optimal path to get the LCS. Try solving it yourself before looking at the answer!

Hidden Mini Quiz — Longest Common Subsequence (LCS)

Check if you understand the basic ideas and DP solution for the LCS problem.

Exercise — Reconstructing the Longest Common Subsequence (LCS)

Given two strings X and Y, after filling the DP table for the Longest Common Subsequence (LCS), the task is to reconstruct the actual longest common subsequence, not just its length.

If there are multiple solutions, it is allowed to output any one.

Input

• First line: string X
• Second line: string Y

Output

• One string — the longest common subsequence

Example

Input:
AGGTAB
GXTXAYB

Output:
GTAB

// Pseudocode
while (i > 0 && j > 0):
  if X[i-1] == Y[j-1]:
    add X[i-1] to LCS
    i--, j--
  else if dp[i-1][j] > dp[i][j-1]:
    i--
  else:
    j--
    

// Reconstructing the Longest Common Subsequence (LCS)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string X, Y;
    cin >> X >> Y;

    int n = X.size(), m = Y.size();

    vector<vector<int>> dp(n + 1, vector(m + 1, 0));

    // Fill the DP table
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            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]);
        }
    }

    // Reconstruct the LCS
    string lcs = "";
    int i = n, j = m;

    while(i > 0 && j > 0) {
        if(X[i-1] == Y[j-1]) {
            lcs.push_back(X[i-1]);
            i--; j--;
        } else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    cout << lcs << endl;
    return 0;
}
    

Challenging Exercise — SIO / National Olympiad Level

The following exercise is intended for advanced practice and requires applying the LCS concept to larger input sequences.

Problem: Longest Common Subsequence of Multiple Strings

Given a set of k strings: S1, S2, ..., Sk, the goal is to find the length of the longest common subsequence that appears in all strings.

Example:

k = 3
S1 = "AGGTAB"
S2 = "GXTXAYB"
S3 = "GTTAB"
Longest common subsequence of all strings: "GTAB", length = 4
  

Guidelines for Solving

• Think about how the standard LCS between two strings can be extended to multiple sequences.
• Define the DP state, e.g., dp[i1][i2][...][ik] or alternatively use iterative pairwise reduction.
• Identify base cases: an empty string gives length 0.
• Use bottom-up tabulation or memoization (top-down) to fill the table and compute the LCS length.
• Analyze memory and time complexity — for larger inputs, optimization or dimension reduction may be necessary.

Note: This exercise is excellent preparation for SIO and national competitions. Try to design the DP approach and transitions first, then implement the code. Do not look at the solution in advance.

Tip: To prepare further, first solve the standard LCS for two strings with subsequence reconstruction, then extend it to multiple strings.

Exercise — Longest Common Subsequence (3 Strings)

Given three strings A, B, and C, the task is to find the longest common subsequence that appears in all three strings.

Example

Input:
AGGTAB
GXTXAYB
GTTAB

Output:
GTAB

// LCS for three strings
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string A, B, C;
    cin >> A >> B >> C;

    int n = A.size(), m = B.size(), p = C.size();

    vector<vector<vector<int>>> dp(
        n + 1,
        vector<vector<int>>(m + 1, vector<int>(p + 1, 0))
    );

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 1; k <= p; k++)
                if(A[i-1] == B[j-1] && A[i-1] == C[k-1])
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else
                    dp[i][j][k] = max({
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    });

    cout << dp[n][m][p] << endl;
    return 0;
}
    

Another Advanced Exercise — SIO / National Olympiad Level

This exercise combines the LCS problem with an additional operation — counting distinct LCS subsequences.

Problem: Counting Distinct LCS Subsequences

Given two strings X and Y, your task is to calculate how many distinct subsequences of maximum LCS length exist.

Example:

X = "ABCBDAB"
Y = "BDCABA"
Maximum LCS length = 4
Number of distinct LCS subsequences = 3
  

Guidelines for Solving

• First, solve the standard LCS to compute the maximum subsequence length.
• Define a DP state that keeps track not only of the LCS length up to indices i,j but also of the number of distinct subsequences of that length.
• Use bottom-up or top-down memoized approach to fill the table.
• Follow base cases: an empty string gives length 0 and 1 subsequence.
• Be careful with duplicates: if the same LCS is counted multiple times, count it only once.
• Finally, dp[n][m] contains the number of distinct LCS subsequences of maximum length.

Note: This exercise is excellent practice for advanced DP applications and requires careful transition analysis and memory optimization.

Tip: Try solving the problem first for small strings and verify the results manually before implementing for larger inputs.