Choose your language!

---

|

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

This lesson focuses on solving LCS problems efficiently and is suitable for programming competitions and practice.

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.

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

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.

Open Quiz

Mini Quiz: Longest Common Subsequence (LCS)

1. What does dp[i][j] represent in the LCS problem?

The length of the LCS of prefixes X[0..i-1] and Y[0..j-1]
The number of common characters in the strings
The longest common substring
Show Answer

2. What do we do when X[i-1] and Y[j-1] are equal?

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

3. Why do we use max(left, top) when the characters do not match?

To choose the better solution by discarding one of the characters
Because it is faster than moving diagonally
Because the DP table must be monotonic
Show Answer

4. What is the time complexity of the standard DP solution for LCS?

O(n + m)
O(n · m)
O(2ⁿ)
Show Answer

5. How is the actual LCS reconstructed?

By tracing back from dp[n][m] through the table
By rerunning the DP algorithm
By sorting the characters
Show Answer

□ Reset Quiz

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

Show Instructions

Instructions — Reconstructing the LCS

The LCS is reconstructed by tracing back through the DP table, starting from dp[n][m].

1. If X[i-1] == Y[j-1]:
   • the character is part of the LCS
   • add it to the result
   • move diagonally: i--, j--
2. If the characters do not match:
   • if dp[i-1][j] > dp[i][j-1] → move up
   • otherwise → move left
3. Since we are moving backwards, the resulting string will be reversed and must be reversed at the end.

// 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--
    

Show Solution

Solution — Reconstructing the LCS (C++)

// 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;
}
    

Complexity

• Time: O(n · m)
• Memory: O(n · m)

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

Show Instructions

Instructions

• This problem is an extension of the standard 2-string LCS to 3 strings.
• Use a 3D DP table: dp[i][j][k].
• dp[i][j][k] represents the length of the LCS of prefixes: A[0..i-1], B[0..j-1], C[0..k-1].
• If the characters match: dp[i][j][k] = dp[i-1][j-1][k-1] + 1
• Otherwise: dp[i][j][k] = max( dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] )
• Time: O(n · m · p), Memory: O(n · m · p)

Show Solution

Solution — LCS for Three Strings (3D DP)

// 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;
}
    

Complexity

• Time: O(n · m · p)
• Memory: O(n · m · p)

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.

Advanced Task: Counting Distinct LCS Subsequences

Given two strings X and Y, you need to compute:

• the maximum length of the Longest Common Subsequence (LCS)
• the number of distinct LCS subsequences of that maximum length

Example

• X = ABCBDAB
• Y = BDCABA

Maximum LCS length = 4
Number of distinct LCS subsequences = 3

Show Instructions

Instructions

1. First, compute the LCS length using the standard DP table len[i][j].
2. Then, introduce an additional DP table cnt[i][j] that represents the number of distinct LCS subsequences of maximum length for prefixes X[0..i-1] and Y[0..j-1].
3. Base case:
   • if i = 0 or j = 0
   • LCS length is 0
   • there is exactly one subsequence — the empty string
4. When characters do not match, duplicate LCSs may appear from the "top" and "left" directions. Therefore, inclusion–exclusion is applied (subtract cnt[i-1][j-1]).
5. The final answer is cnt[n][m], counting only subsequences whose length equals len[n][m].

Tip: Try first with short strings and manually list all LCSs to ensure the same subsequence is not counted multiple times.

Show Solution

Solution — Counting Distinct LCS Subsequences (C++)

// Counting distinct LCS subsequences
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABA";

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

    vector<vector<int>> len(n + 1, vector<int>(m + 1, 0));
    vector<vector<long long>> cnt(n + 1, vector<long long>(m + 1, 0));

    // Base cases
    for(int i = 0; i <= n; i++) cnt[i][0] = 1;
    for(int j = 0; j <= m; j++) cnt[0][j] = 1;

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

            if(X[i-1] == Y[j-1]) {
                len[i][j] = len[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
            } else {
                len[i][j] = max(len[i-1][j], len[i][j-1]);

                long long ways = 0;
                if(len[i-1][j] == len[i][j])
                    ways += cnt[i-1][j];
                if(len[i][j-1] == len[i][j])
                    ways += cnt[i][j-1];

                if(len[i-1][j] == len[i][j] &&
                   len[i][j-1] == len[i][j] &&
                   len[i-1][j-1] == len[i][j]) {
                    ways -= cnt[i-1][j-1];
                }

                cnt[i][j] = max(0LL, ways);
            }
        }
    }

    cout << "Maximum LCS length: " << len[n][m] << endl;
    cout << "Number of distinct LCS subsequences: " << cnt[n][m] << endl;

    return 0;
}
    

Why this approach works

• len[i][j] ensures that only optimal subsequences are counted
• cnt[i][j] counts distinct LCSs without duplicates
• Inclusion–exclusion removes repeated paths in the DP table
• This pattern applies to many "counting optimal solutions" problems

Detailed explanation of the logic

The dynamic table len determines the length of the optimal LCS, while cnt counts how many distinct LCSs of that length exist.

Each cell (i, j) represents the problem for prefixes X[0..i-1] and Y[0..j-1]. An LCS can be formed:

• diagonally (↖) — if characters match
• from top (↑) — if we ignore a character from X
• from left (←) — if we ignore a character from Y

When the optimal length can be obtained both from top and left, the same LCS sequences appear in both directions. Therefore, the inclusion–exclusion principle is applied, subtracting cnt[i-1][j-1].

This ensures that each distinct LCS string is counted exactly once, regardless of the number of paths through the DP table.

In this example, there are exactly three distinct LCSs of length 4:

BCBA
BDAB
BCAB
      

Branching in this example

This problem does not have only one LCS, but multiple distinct subsequences of the same maximum length. From the DP table, there are three different paths producing an LCS of length 4.

Visual representation (by letters):

• LCS #1
  B  C  B  A
• LCS #2
  B  D  A  B
• LCS #3
  B  C  A  B

□ All three subsequences:

• have maximum length 4
• appear as subsequences in X and Y
• are distinct as strings

---

Why there aren’t more?

Although the DP table contains many paths from cell (n, m) to (0, 0), different paths can produce the same LCS string.

For example, the following two paths:

↖ ↑ ← ↖     and     ↖ ← ↑ ↖
      

can lead to the same character sequence. Even though the paths are different, the resulting LCS string is the same, so it must be counted only once.

---

Algorithmic intuition

In addition to the standard DP table for length:

dpLen[i][j] = LCS length for X[0..i-1] and Y[0..j-1]
      

we introduce another table:

dpCount[i][j] = number of distinct LCS subsequences
                of maximum length
      

Basic rules:

1. If characters match:

   
   count[i][j] = count[i-1][j-1]
             

   Each optimal LCS is extended by that common character.

2. If characters do not match:
   • If dpLen[i-1][j] > dpLen[i][j-1]:

     
     count[i][j] = count[i-1][j]
                   

   • If dpLen[i][j-1] > dpLen[i-1][j]:

     
     count[i][j] = count[i][j-1]
                   

   • If lengths are equal:

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

     Subtracting count[i-1][j-1] removes duplicates coming from both directions.

□ Subtraction is crucial — without it, the same LCS subsequence would be counted multiple times.

---

Final result for the example

X = ABCBDAB
Y = BDCABA

Maximum LCS length = 4
Number of distinct LCS = 3
      

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!

Mini Quiz: LCS Practice

Check your understanding of the Longest Common Subsequence (LCS) using this example.

Open Quiz

1. What is the length of the LCS for X = "XMJYAUZ" and Y = "MZJAWXU"?

3
4
5
Show Answer

2. Which of the following is an LCS for the same strings?

"MJUZ"
"MJAU"
"XZJU"
Show Answer

3. If two characters do not match at dp[i][j], what is the DP rule to follow?

Take the maximum of dp[i-1][j] and dp[i][j-1]
Always move diagonally
Set dp[i][j] to 1
Show Answer

□ Reset Quiz

4. Related Pages

• Introduction to DP — Basic Idea
• DP: Fibonacci with Memoization
• DP: Knapsack Problem
• DP: Subset Sum (coming soon)

The next lesson could be the Subset Sum problem or additional LCS examples for practice and competitions.

---

Previous
​|< DP: Knapsack problem

Next
DP: Subset Sum problem >|

---