Longest Common Subsequence

Problem

Return the length of the longest common subsequence of strings a and b using dynamic programming.

Let dp[i][j] be the LCS length of the first i characters of a and the first j characters of b. On a character match extend the diagonal; otherwise take the better of the state above and the state to the left. An empty string gives length 0.

Hint

Characters must appear in both strings in the same relative order, but not necessarily consecutively.

Test cases

case 1

in: ["abcde","ace"]

expected: 3

case 2

in: ["abc","abc"]

expected: 3

case 3

in: ["abc","def"]

expected: 0

case 4

in: ["","abc"]

expected: 0

case 5

in: ["abcba","abcbc"]

expected: 4

Starter codePython

def lcs_length(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor