Python longest common subsequence: rolling-row DP and its limits

Operation contract

The fixture compares two bounded event-label strings. Matching characters extend the previous row’s diagonal result; differing characters retain the larger result from dropping one side’s current character. Only the previous and current rows are needed when the result is a length. Keeping a complete path reconstruction would need another storage or recomputation plan.

Failure and ownership boundary

This is not longest common substring and not an edit script. The string inputs are limited to 128 code points; their equality is exact. A document comparison service also needs tokenization and a work budget because the product of input lengths drives this recurrence. Python prefix-function search: overlapping matches without rescanning answers a different question.

Working program

def common_event_length(first, second):
    if type(first) is not str or type(second) is not str or max(len(first), len(second)) > 128:
        raise ValueError("sequence budget")
    if len(first) < len(second):
        first, second = second, first
    previous = [0] * (len(second) + 1)
    for first_event in first:
        current = [0]
        for index, second_event in enumerate(second, 1):
            current.append(previous[index - 1] + 1 if first_event == second_event
                           else max(previous[index], current[-1]))
        previous = current
    return previous[-1]

print(common_event_length("PACK", "PARK"))
print(common_event_length("", "PACK"))

Output

3
0

Costs and limits

Time is O(n*m), with O(min(n,m)) row storage. The output is a length, so this program does not retain the actual chosen subsequence.

Common Mistakes

• A subsequence can skip entries; a substring cannot.
• A linear-space length result is not automatically a linear-space reconstruction.

Connected lessons

Python memoization: cache bounded states without hiding recursion depth, Python prefix-function search: overlapping matches without rescanning, Python 0/1 knapsack: descending capacity prevents item reuse.

Related Python operation checks

Python edit distance: rolling rows for insert, delete and replace.

Follow the service contract

Python longest increasing subsequence: reconstruct a strict sequence from tail candidates.