# Title: Longest common subsequence
# Heading: Python Program for the Longest Common Subsequence (LCS)
# Level: advanced
# Tags: longest common subsequence, lcs, dynamic programming, dp, strings
# Time: O(m × n)
# Space: O(m × n)
# About: Finds the longest run of letters that appears in the same order, not always side by side, in both of two strings, with a table.

def lcs(a, b):
    """The longest common subsequence of the strings a and b."""
    # length[i][j]: the LCS length of a[:i] and b[:j]
    length = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                length[i][j] = length[i - 1][j - 1] + 1
            else:
                length[i][j] = max(length[i - 1][j], length[i][j - 1])

    # Walk back from the last cell to read the letters
    letters = []
    i, j = len(a), len(b)
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            letters.append(a[i - 1])
            i -= 1
            j -= 1
        elif length[i - 1][j] >= length[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(letters))


result = lcs("STONE", "LONGEST")
print("Longest common subsequence:", result)
print("Its length:", len(result))