Longest Common Subsequence
The drill: Two strings — find the length of the longest sequence of characters that appears in both, in the same relative order, without needing the characters to sit next to each other.
Two strings arrive, and the task is to find the length of the longest sequence of characters that shows up in both — in the same relative order in each — without those characters needing to sit next to each other in either string.
Characters can be skipped freely on either side to line the subsequence up; the only rule is that the relative order of the chosen characters can't be rearranged. An empty subsequence is always trivially shared, so the answer is never negative.
Only the length of that longest shared subsequence is needed, not the subsequence's actual characters.
- strings can be empty, and can contain lowercase or mixed-case letters
- strings stay short enough for an O(m·n) table
- matched characters don't need to be adjacent within either string
- only the length is required, not the subsequence itself
HINT 1 THE NUDGE
Compare the last character of each string. If they match, that pair belongs in some longest common subsequence — what question is left once you strip it off?
HINT 2 THE STRUCTURE
If the last characters differ, the answer for the two full strings is the better of two smaller answers: drop the last character of the first string, or drop the last character of the second.
HINT 3 ONE STEP FROM THE ANSWER
DP table dp[i][j] = LCS length using the first i characters of text1 and first j of text2. Match → dp[i-1][j-1] + 1. Mismatch → max(dp[i-1][j], dp[i][j-1]).
Row 0 and column 0 both start at zero — matching an empty prefix against anything shares nothing.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
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]class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
def lcs(i, j):
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
return 1 + lcs(i + 1, j + 1)
return max(lcs(i + 1, j), lcs(i, j + 1))
return lcs(0, 0)class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}class Solution {
private String a, b;
public int longestCommonSubsequence(String text1, String text2) {
a = text1;
b = text2;
return lcs(0, 0);
}
private int lcs(int i, int j) {
if (i == a.length() || j == b.length()) {
return 0;
}
if (a.charAt(i) == b.charAt(j)) {
return 1 + lcs(i + 1, j + 1);
}
return Math.max(lcs(i + 1, j), lcs(i, j + 1));
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED