# Longest common subsequence in Java

Photo by Pankaj Patel on Unsplash

In this post we will see how to solve a problem that is to look for the longest common subsequence of two Strings that we receive as input parameters.

To solve this we will use a technique that is called dynamic programming. This technique uses the fact that a problem can be break into sub-problems in a recursive manner and using the results of previous sub-problems allow us to avoid repeating previous computations.

In this particular problem we will use a matrix called `DP`

that at any given position (i, j) will have calculated the previous number characters that form a subsequence in both input Strings.

```
public class LongestCommonSubsequence {
public int calculateLongestCommonSubsequence(String a, String b) {
int N = a.length();
int M = b.length();
if (N == 0 || M == 0) {
return 0;
}
int[][] DP = new int[N][M];
if (a.charAt(0) == b.charAt(0)) {
DP[0][0] = 1;
}
for (int i = 1; i < N; i++) {
DP[i][0] = (DP[i - 1][0] == 1 || a.charAt(i) == b.charAt(0)) ? 1 : 0;
}
for (int j = 1; j < M; j++) {
DP[0][j] = (DP[0][j - 1] == 1 || a.charAt(0) == b.charAt(j)) ? 1 : 0;
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
DP[i][j] = Math.max(DP[i - 1][j], DP[i][j - 1]);
if (a.charAt(i) == b.charAt(j)) {
DP[i][j] = Math.max(DP[i][j], 1 + DP[i - 1][j - 1]);
}
}
}
return DP[N - 1][M - 1];
}
public static void main(String[] args) {
LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
System.out.println(longestCommonSubsequence.calculateLongestCommonSubsequence("alex", "alexander"));
}
}
```

### Conclusion

In this post we have seen how to solve the problem of finding the longest common subsequence between two Strings that we receive as input parameters using dynamic programming.

## Comments