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()
}