Longest Common Subsequence

Explanation & Solution

Description

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.

Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters

Approach

Dynamic Programming pattern

1. Create the DP Table

Create a 2D array dp of size (m+1) x (n+1), initialized to 0
dp[i][j] represents the length of the longest common subsequence of text1[0..i-1] and text2[0..j-1]
The first row and first column are 0 because the LCS of any string with an empty string is 0

2. Fill the Table Row by Row

For each character text1[i-1] and text2[j-1]:
If the characters match: dp[i][j] = dp[i-1][j-1] + 1
We extend the LCS of the two prefixes by 1
If the characters don't match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
We take the better result from either skipping a character from text1 or skipping a character from text2

3. Character Match Case

When text1[i-1] === text2[j-1], both strings contribute this character to the LCS
We look diagonally at dp[i-1][j-1] (the LCS without either character) and add 1

4. Character Mismatch Case

When characters differ, the LCS does not include both characters
We take the maximum of:
dp[i-1][j]: LCS excluding the current character of text1
dp[i][j-1]: LCS excluding the current character of text2

5. Return the Result

dp[m][n] contains the length of the LCS of the full strings
Return this value

Key Insight

This is a foundational 2D dynamic programming problem that demonstrates how to compare two sequences character by character
The diagonal transition (match case) is what builds up the subsequence, while the max of top/left (mismatch case) preserves the best result so far

Time

O(m * n) where m and n are the lengths of the two strings

Space

O(m * n) for the 2D DP table (can be optimized to O(min(m, n)) with rolling array)

Solution Code

Word Break

0/1 Knapsack