lcs problem statement given two sequences find the length of longest subsequence present in both of them a subsequence is a sequence that appears in the same relative order but not necessarily continuous example abc abg are subsequences of abcdefgh finds the longest common subsequence between two strings also returns the the subsequence found parameters x str one of the strings y str the other string returns lmn int the length of the longest subsequence also equal to lenseq seq str the subsequence found longestcommonsubsequenceprogramming gaming 6 gaming longestcommonsubsequencephysics smartphone 2 ph longestcommonsubsequencecomputer food 1 o find the length of strings declaring the array for storing the dp values finds the longest common subsequence between two strings also returns the the subsequence found parameters x str one of the strings y str the other string returns l m n int the length of the longest subsequence also equal to len seq seq str the subsequence found longest_common_subsequence programming gaming 6 gaming longest_common_subsequence physics smartphone 2 ph longest_common_subsequence computer food 1 o find the length of strings declaring the array for storing the dp values noqa e741
def longest_common_subsequence(x: str, y: str):
    
    

    assert x is not None
    assert y is not None

    m = len(x)
    n = len(y)

    
    l = [[0] * (n + 1) for _ in range(m + 1)]  

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            match = 1 if x[i - 1] == y[j - 1] else 0

            l[i][j] = max(l[i - 1][j], l[i][j - 1], l[i - 1][j - 1] + match)

    seq = ""
    i, j = m, n
    while i > 0 and j > 0:
        match = 1 if x[i - 1] == y[j - 1] else 0

        if l[i][j] == l[i - 1][j - 1] + match:
            if match == 1:
                seq = x[i - 1] + seq
            i -= 1
            j -= 1
        elif l[i][j] == l[i - 1][j]:
            i -= 1
        else:
            j -= 1

    return l[m][n], seq


if __name__ == "__main__":
    a = "AGGTAB"
    b = "GXTXAYB"
    expected_ln = 4
    expected_subseq = "GTAB"

    ln, subseq = longest_common_subsequence(a, b)
    print("len =", ln, ", sub-sequence =", subseq)
    import doctest

    doctest.testmod()