In this article, we will learn to resolve the Longest Common Subsequence problem by using a dynamic programming algorithm

## Problem

• Given two strings, `S` of length `m` and `T` of length `n`

• Write an algorithm to find the length of the longest common subsequence (LCS) of both `S` and `T`

## Example 1

• Input: given two strings "ABCD" and "ACBAD"

• Expected output: 3

• Explanation: Both the given strings have 2 longest common subsequences: ABD and ACD

## Example 2

• Input: given two strings "XMJYAUZ" and "MZJAWXU"

• Expected output: 4

• Explanation: Both the given strings have 1 longest common subsequence: MJAU

## Approach: Bottom-Up Dynamic Programming

Consider the two given string S = "ABCD" and T = "ACBAD", say L(i, j) with i and j starting from 1 is the length of the LCS of S and T until i-1 and j-1 characters

• With i = 1 and j run from 1 to 5: L(i, j) = 1, S(i-1) and T(j-1) has 1 common subsequence 'A'
``````i = 1, j = 1 -> 5
A C B A D
A 1 1 1 1 1
B
C
D
``````
• With i = 2 and j run from 1 to 5: L(i, j) = 2, S(i-1) and T(j-1) has 1 common subsequence 'AB'
``````i = 2, j = 1 -> 5
A C B A D
A 1 1 1 1 1
B 1 1 2 2 2
C
D
``````
• With i = 3 and j run from 1 to 5: L(i, j) = 2, S(i-1) and T(j-1) has 2 common subsequences 'AB' and 'AC'
``````i = 3, j = 1 -> 5
A C B A D
A 1 1 1 1 1
B 1 1 2 2 2
C 1 2 2 2 2
D
``````
• With i = 4 and j run from 1 to 5: L(i, j) = 3, S(i-1) and T(j-1) has 2 length-3 common subsequences 'ABD' and 'ACD', 5 length-2 common subsequences 'AB', 'AC', 'AD', 'BD', and 'CD'
``````i = 4, j = 1 -> 5
A C B A D
A 1 1 1 1 1
B 1 1 2 2 2
C 1 2 2 2 2
D 1 2 2 2 3
``````

From the above solutions break down, at every step we have 2 choices

• If S(i-1) = T(j-1), L(i, j) = L(i-1, j-1) + 1

• Else, L(i, j) = max between L(i-1, j) and L(i, j-1)

``````public class DP_LongestCommonSubsequence {
static int lengthOfLongestCommonSubsequence(String S, String T) {
int m = S.length();
int n = T.length();
int[][] lengths = new int[m+1][n+1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if(S.charAt(i-1) == T.charAt(j-1)) {
lengths[i][j] = lengths[i-1][j-1] + 1;
} else {
lengths[i][j] = Math.max(lengths[i-1][j], lengths[i][j-1]);
}
}
}

return lengths[m][n];
}

public static void main(String[] args) {
``````3