Back to Study Material Data Structures and Algorithms

Longest Common Subsequence

The longest common subsequence (LCS) problem asks: given two sequences X of length m and Y of length n, find the length of the longest sequence that appear...

Longest Common Subsequence

Problem Definition and Recursive Structure

The longest common subsequence (LCS) problem asks: given two sequences X of length m and Y of length n, find the length of the longest sequence that appears as a subsequence in both X and Y. A subsequence preserves the relative order of elements but does not require them to be contiguous. For example, "ACE" is a subsequence of "ABCDE" but "AEC" is not.

LCS differs from the longest common substring problem, where characters must be contiguous. "ABCBDAB" and "BDCAB" have LCS "BCAB" or "BDAB" of length 4, but their longest common substring is "AB" of length 2. This distinction matters because the two problems have different DP formulations.

The recursive structure: let LCS(i, j) be the LCS length of the first i characters of X and first j characters of Y. Base cases: LCS(0, j) = 0 and LCS(i, 0) = 0. Recurrence: if X[i] == Y[j], then LCS(i, j) = 1 + LCS(i-1, j-1). Otherwise, LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)). The intuition: if the last characters match, they must be part of the LCS; if not, we try excluding one character from each sequence separately and take the better result.

Time complexity with DP: O(m*n) for filling the table. Space complexity: O(m*n) for the full table, or O(min(m, n)) with a rolling array. Reconstructing the actual subsequence (not just its length) requires the full table and a backtracking pass.

Interview tip: Clarify whether you need the LCS length or the actual subsequence. Length requires less space and simpler code. The actual subsequence requires keeping track of choices during table construction, which adds complexity but is frequently what interviewers want in follow-up questions.

Building and Reading the DP Table

To build the LCS DP table, create a 2D array dp of size (m+1) by (n+1), where m = len(X) and n = len(Y). Initialize the first row and first column to 0. Fill in row-major order: for i from 1 to m, for j from 1 to n, if X[i-1] == Y[j-1] set dp[i][j] = dp[i-1][j-1] + 1; otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

A concrete example: X = "AGGTAB", Y = "GXTXAYB". Build the 7x8 table. When X[i-1] matches Y[j-1], diagonal + 1. When they differ, take the maximum of left and top. The value at dp[6][7] gives the LCS length, which is 4, corresponding to "GTAB".

To reconstruct the LCS, start at dp[m][n] and trace backwards. If X[i-1] == Y[j-1], this character is in the LCS; record it and move diagonally to dp[i-1][j-1]. If dp[i-1][j] > dp[i][j-1], move up (exclude X[i-1]). Otherwise move left (exclude Y[j-1]). Collect characters in reverse, then reverse the result. This backtracking is O(m+n) after the table is built.

Multiple LCS solutions may exist. The backtracking procedure above finds one; it may differ depending on tie-breaking when dp[i-1][j] == dp[i][j-1]. If the problem asks for the lexicographically smallest LCS, you need to modify the tie-breaking rule accordingly.

Interview tip: Walk through the table construction on a small example (four-character strings) during the interview. Drawing the 5x5 table explicitly, filling it cell by cell, and then tracing the backtracking path makes your explanation concrete and leaves no doubt about correctness.

Applications and Variations

LCS has a surprisingly broad range of applications beyond string comparison. In bioinformatics, LCS measures similarity between DNA sequences (e.g., identifying conserved gene regions across species). In version control systems, diff tools like Unix diff compute the LCS of two file versions to identify the minimum set of changed lines. In spell correction, LCS-based similarity measures help rank candidate corrections.

The edit distance (Levenshtein distance) problem is closely related to LCS. Edit distance counts the minimum number of insertions, deletions, and substitutions to transform one string into another. The relationship: edit_distance(X, Y) = (m - LCS_length) + (n - LCS_length) = m + n - 2 * LCS_length, when only insertions and deletions are allowed (no substitutions). Adding substitutions changes the recurrence slightly.

The shortest common supersequence (SCS) is another LCS variant: find the shortest sequence that contains both X and Y as subsequences. SCS length = m + n - LCS_length, and the actual SCS can be reconstructed using the same LCS backtracking table.

The longest palindromic subsequence of a string S is the LCS of S and its reverse. This is a classic trick that reduces a new problem to LCS without any new DP derivation. Similarly, the longest bitonic subsequence (first increasing then decreasing) can be solved by combining a LIS from left and a LIS from right.

Interview tip: If given a problem about comparing two sequences, immediately think about whether LCS or edit distance applies. Being able to say "this reduces to LCS" and explaining the reduction quickly is a valuable problem-solving pattern that many candidates miss.