Longest Common Subsequence

Problem

Code review tools and plagiarism detectors measure similarity between two sequences by finding their longest common subsequence. Given two strings, return the length of their longest common subsequence - the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous).

Input: text1="abcde", text2="ace"  → 3   (a, c, e)
Input: text1="abc", text2="abc"    → 3   (full strings match)
Input: text1="abc", text2="def"    → 0   (no characters in common)

Verification

Trace 'abc' vs 'abc': dp[1][1]=1 (a==a), dp[1][2]=1, dp[1][3]=1. dp[2][1]=1, dp[2][2]=2 (b==b), dp[2][3]=2. dp[3][1]=1, dp[3][2]=2, dp[3][3]=3 (c==c). Return 3.

Solution

Approach: 2D tabulation over prefixes of both strings (sequence alignment).

Define dp[i][j] as the LCS length of the first i characters of text1 and the first j of text2. The grid has an extra row 0 and column 0 of zeros: an empty prefix shares nothing, so those are the base cases. Filling proceeds by the last characters of each prefix. If text1[i-1] == text2[j-1], that shared character must extend whatever was optimal before both of them, so dp[i][j] = dp[i-1][j-1] + 1 - the diagonal plus one. If they differ, the LCS cannot use both, so the best is to drop one character from one string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]), the better of skipping text1's last char or text2's last char. Rows fill top to bottom and left to right, so every neighbor a cell reads (above, left, diagonal) is already final. The answer accumulates in the bottom-right cell dp[rows-1][cols-1]. The i-1/j-1 offset is the recurring trap: the table is indexed one ahead of the strings because of the zero padding. Trace abc vs abc: the diagonal increments at every match, giving 1, 2, 3.

Edge cases: An empty input string makes either rows or cols equal to 1, so the loops never run and dp[rows-1][cols-1] stays 0 - the correct empty-overlap answer. Strings with no common characters never hit the match branch and return 0.

Complexity: O(m x n) time, O(m x n) space - one cell per prefix pair, each computed in O(1); reducible to two rows if only the length is needed.