Algorithms – Dynamic Programming – Longest Common Subsequence (LCS)

Let’s implement the following problem:

Given two strings A and B of equal lengths, containing only lower case letters, our job is to count the minimum number of changes required on string A to make it equal to string B.

Let’s first talk what is a subsequence. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. 

LCS for “ABCDGH” and “AEDFHR”   => length 3
LCS for “AGGTAB” and “GXTXAYB”   => length 4 

The algorithm is quite simple.

Given two array of characters X and Y, of length m and n respectively:

  • IF last characters of both sequences match (X[m-1] == Y[n-1]):
    • LCS(X[0, m-1], Y[0, n-1] = 1 + LCS(X[0, m-2], Y[0, n-2]
  • Else:
    • LCS(X[0, m-1], Y[0, n-1] = MAX( LCS(X[0, m-2], Y[0, n-1]), LCS(X[m-1], Y[0, n-2]) )

Still not clear? See the following code.

The problem with this is the following: We calculate the same code multiple times:

Let’s check the code which uses the dynamic programming approach.

And this is an example of how it works.

You may also like...

Leave a Reply