DSA Longest Common Subsequence

How it works

The dynamic program compares prefixes of two strings. Equal final characters extend a smaller shared result; otherwise one side’s final character is skipped. A second walk reconstructs one longest common subsequence, with a deterministic tie policy but no promise of lexicographically smallest output. Python strings are sequences of Unicode code points, so this is not a locale-aware grapheme matching algorithm. Large tables are rejected by an explicit slot budget.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as common-subsequence.py and run python common-subsequence.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def longest_common_subsequence(first, second):
    if not isinstance(first, str) or not isinstance(second, str):
        raise ValueError("String inputs required")
    if (len(first) + 1) * (len(second) + 1) > 100000:
        raise ValueError("Teaching table budget exceeded")
    table = [[0] * (len(second) + 1) for _ in range(len(first) + 1)]
    for row in range(1, len(first) + 1):
        for column in range(1, len(second) + 1):
            if first[row - 1] == second[column - 1]:
                table[row][column] = table[row - 1][column - 1] + 1
            else:
                table[row][column] = max(table[row - 1][column], table[row][column - 1])
    row, column, result = len(first), len(second), []
    while row and column:
        if first[row - 1] == second[column - 1]:
            result.append(first[row - 1])
            row -= 1
            column -= 1
        elif table[row - 1][column] >= table[row][column - 1]:
            row -= 1
        else:
            column -= 1
    return "".join(reversed(result))

result = longest_common_subsequence("orchard", "chart")
print(result, len(result))
print(repr(longest_common_subsequence("", "oak")))

Expected result

char 4
''

The four characters appear in both strings in order. The empty input produces an empty result. The property review independently verifies both subsequence membership and optimal length, because checking only that a returned string appears in each input would allow a needlessly short answer.

Time, space and assumptions

Time and table space are O(nm) for input lengths n and m. Reconstruction is O(n+m) steps; smaller-space length-only algorithms have a different witness-recovery design.