# Longest Common Subsequence

we can say that two DNA strands are similar

- if one is a substring of the other. In our example, neither S1 nor S2 is a substring of the other.
- Alternatively,we could say that two strands are similar if the number of changes needed to turn one into the other is small.
- Yet another way to measure the similarity of strands S1 and S2 is by finding a third strand S3 in which the bases in S3 appear in each of S1 and S2; these bases must appear in the same order, but not necessarily consecutively. The longer the strand S3 we can find, the more similar S1 and S2 are.

In the longest-common-subsequence problem, we are given two sequences X = (x1, x2,… xm) and Y = (y1,y2,….yn) and wish to find a maximum length common subsequence of X and Y

```
fun largestCommonSubsequence(x: String, y: String): Int {
val dp = Array(x.length + 1) { IntArray(y.length + 1) { 0 } }
for (i in x.indices) {
for (j in y.indices) {
if (x[i] == y[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1
} else {
dp[i + 1][j + 1] = maxOf(dp[i][j + 1], dp[i + 1][j])
}
}
}
return dp.last().last()
}
```