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) {
System.out.println(lengthOfLongestCommonSubsequence("ABCD", "ACBAD"));
System.out.println(lengthOfLongestCommonSubsequence("XMJYAUZ", "MZJAWXU"));
}
}
```

- Output

```
3
4
```

- Time complexity is O(mn) and space complexity is O(mn) where m and n are the numbers of elements in the two given sequences