Longest Common Subsequence

Longest subsequence two strings share (not necessarily contiguous). Diff tools and DNA alignment are built on this table: match → diagonal + 1, else max of top/left.

Category

Dynamic Programming

Time complexity

O(n·m)

Space complexity

O(n·m)

Pseudocode

grid: string A × string B
match: diagonal + 1
no match: max(top, left)
length at bottom-right

Reference implementation

if A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j],
                   dp[i][j-1])

Open the interactive Longest Common Subsequence visualisation →