Grokking Dynamic Programming Interview in Python/

...

/

Longest Common Subsequence

Longest Common Subsequence

Let's solve the Longest Common Subsequence problem using Dynamic Programming.

We'll cover the following...

Statement

Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.

A subsequence is a string formed by removing some characters from the original string, while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.

If there is no common subsequence, then return 0.

Let’s say you have the following two strings:

  • “cloud”
  • “found”

The longest common subsequence between these two strings is “oud”, which has a length of 33.

Constraints:

  • 1<=1 <= str1.length <=500<= 500
  • 1<=1 <= str2.length <=500<= 500
  • str1 and str2 contain only lowercase English characters.

Examples

No.

str1

str2

Length

1

"bald"

"bad"

3

2

"nocturnal"

"nick"

2

3

"card"

"tissue"

0

Try it yourself

Implement your solution in the following coding playground.

Press + to interact
Python
usercode > main.py
def longest_common_subsequence(str1, str2):



    # Write your code here

    

    # your code will replace the placeholder return statement below

    return -1
Longest Common Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to compare the characters of both strings based on the following rules:

  • If the current characters of both strings match, we move one position ahead in both strings.

  • If the current characters of both strings do not match, we recursively calculate the maximum length of moving one character forward in any one of the two strings i.e., we check if moving a character forward in either the first string or the second will give us a longer subsequence.

  • If we reach the end of either of the two strings, we return 00.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

# Helper function with updated signature: i is current index in str1, j is current index in str2
def longest_common_subsequence_helper(str1, str2, i, j): 
    # base case
    if i == len(str1) or j == len(str2): 
        return 0
    # if current characters match, increment 1
    elif str1[i] == str2[j]:  
        return 1 + longest_common_subsequence_helper(str1, str2, i+1, j+1)
    
    # else take max of either of two possibilities
    return max(longest_common_subsequence_helper(str1, str2, i+1, j), longest_common_subsequence_helper(str1, str2, i, j+1))
def longest_common_subsequence(str1, str2):
    return longest_common_subsequence_helper(str1, str2, 0, 0)
# Driver code
def main():
    first_strings = ["qstw", "setter", "abcde", "partner", "freedom"]
    second_strings = ["gofvn", "bat", "apple", "park", "redeem"]
    # You can uncomment the lines below and check how this recursive solution causes a time-out 
    # first_strings.append("sjcneiurutvmpdkapbrcapjru")
    # second_strings.append("oidhfwepkxwebyurtunvidqlscmjbg")
    for i in range(len(first_strings)):
        print(i + 1, ".\t str1:",first_strings[i],"\n\t", \
                        "str2:", second_strings[i],"\n\n\t", \
                        "The length of the longest common subsequence is:", longest_common_subsequence(first_strings[i], second_strings[i])) \
                
        print("-" * 100)
if __name__ == '__main__':
    main()
Longest Common Subsequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity

The time complexity of the naive approach is ...

Access this course and 1400+ top-rated courses and projects.