⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1143) before relying on it.

Longest Common Subsequence

An interactive visualization of the dynamic programming approach to finding the longest common subsequence. Watch how the DP table fills row by row to compute the LCS length between two strings.

Dynamic Programming LeetCode 1143 ↗ Medium

The Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Interactive Visualization

Text1

Text2

Preset

Speed:

DP Table

Code

fun longestCommonSubsequence(text1: String, text2: String): Int {    val m = text1.length    val n = text2.length    val dp = Array(m + 1) { IntArray(n + 1) }    for (i in 1..m) {        for (j in 1..n) {            if (text1[i - 1] == text2[j - 1]) {                dp[i][j] = dp[i - 1][j - 1] + 1            } else {                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])            }        }    }    return dp[m][n]}

def longestCommonSubsequence(text1, text2):    m, n = len(text1), len(text2)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m + 1):        for j in range(1, n + 1):            if text1[i-1] == text2[j-1]:                dp[i][j] = dp[i-1][j-1] + 1            else:                dp[i][j] = max(dp[i-1][j], dp[i][j-1])    return dp[m][n]

Status

Press Step or Play to begin.

How It Works

Key Insight

The longest common subsequence problem can be solved using dynamic programming. We build a 2D table where dp[i][j] represents the length of the LCS of the first i characters of text1 and the first j characters of text2.

The Recurrence Relation

Base case: dp[0][j] = 0 and dp[i][0] = 0 for all i and j (empty string has LCS length 0)
If characters match: text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1
If characters don't match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the best from excluding either character)
Final answer: dp[m][n] where m and n are the lengths of the two strings

Complexity

Time O(m × n)

Space O(m × n)

We fill a table of size m × n where m and n are the lengths of the two input strings. Each cell is computed in constant time. The space can be optimized to O(min(m, n)) by only keeping two rows.