Learn practical skills, build real-world projects, and advance your career

Longest Common Subsequence

QUESTION 1: Write a function to find the length of the longest common subsequence between two sequences. E.g. Given the strings "serendipitous" and "precipitation", the longest common subsequence is "reipito" and its length is 7.

A "sequence" is a group of items with a deterministic ordering. Lists, tuples and ranges are some common sequence types in Python.

A "subsequence" is a sequence obtained by deleting zero or more elements from another sequence. For example, "edpt" is a subsequence of "serendipitous".

General case


Test cases

  1. General case (string)
  2. General case (list)
  3. No common subsequence
  4. One is a subsequence of the other
  5. One sequence is empty
  6. Both sequences are empty
  7. Multiple subsequences with same length
    1. “abcdef” and “badcfe”
def len_lcs(seq1, seq2):
!pip install jovian --upgrade --quiet
import jovian 
[jovian] Attempting to save notebook.. [jovian] Updating notebook "haoyu777777/dynamic-programming-problems" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/haoyu777777/dynamic-programming-problems