Longest Common Subsequence

Input Strings

String A

String B

Playback

Speed

LCS Result

—

Stats

LCS length—

Cells filled0

Similarity—

Legend

Current cell

Match: dp[i-1][j-1]+1

No match: took dp[i-1][j]

No match: took dp[i][j-1]

Traceback path

LCS character

Preset Examples

How it works

Build a 2D table where dp[i][j] = LCS length of A[0..i-1] and B[0..j-1].

Recurrence:
If A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

After filling, traceback from dp[m][n] to dp[0][0] recovers the actual LCS string.

String A

String B

Press Play or Step to start the LCS visualization.