1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Solution:

Let’s start with the recursive approach. What can we do to find the common characters ? Take a = “abcde” and b = “ce”. Characters at a[0] != b[0]. So we can either move towards right from a and compare a[1] to b[0], or we can move towards right from b and compare a[0] to b[1]. If they are equal, we can move right from both a and b. If not then we can keep on following the movement towards right first from a and then from b. Lets see this in recursive code.

a = "abcde"
b = "ce"
def LCS(i, j): # i and j are pointers for a and b respectively
    if i >= len(a) or j >= len(b): # If we reach at the end of any of the strings, return as 0 as there cant be anything common with null.
        return 0
    elif a[i] == b[j]:
        return 1 + LCS(i+1, j+1) # if characters match, move towards right from both the strings and increase common character count by 1
    else:
        return max(LCS(i+1, j), LCS(i, j+1)) # if characters dont match then move either from a or from b and take maximum as optimal answer as we are searching for longest.

Time complexity: exponential

Lets try dynamic programming approach for this:

a = "abcde"
b = "ace"
dp = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)]
# creating a table to store the answers
for i in range(1, len(a)+1): # iterating on first string as rows of table
  for j in range(1, len(b)+1): # iterating on second string as cols of table
    if a[i-1] == a[j-1]: # if characters match, then take the prev diagonal element and add 1
      dp[i][j] = 1 + dp[i-1][j-1]
    else: # if it doesnt match, take max of up and down
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[i][j]) # print last cell which has the answer

In DP, each cell asks one question.

''    [[0, 0, 0, 0],
a     [0, 1, 1, 1],
b     [0, 1, 1, 1],
c     [0, 1, 2, 2],
d     [0, 1, 2, 2],
e     [0, 1, 2, 3]]
       '' a  c  e

So first row and first col is set as 0. It just adds as the initial layer representing if there are no characters in string a, then first row is 0 and if no characters in b, then first column in 0.

Now any cell asks a question. Take cell dp[5][3] for example. It asks if we take (5–1) characters from string a and (3–1) characters from string b, what is the maximum length of common subsequence we can get. To solve this we look if a[5–1] == b[3–1] i.e, ‘e’ == ‘e’. Since they are equal we can increase one to the prev answer at the diagonal dp[5–1][3–1] (dp[4][3]). This diagonal represents the lcs if we take (4–1) characters from string a and (3–1) from b. And so on. We are always subtracting 1 as we have the first col and row as padding for null strings.

Please ask questions. Thanks!!