Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem is a classic string-based Dynamic Programming challenge. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguously. For example, "abc" is a subsequence of "aXbYcZ".

The goal is to find the length of the longest subsequence present in two given strings.

1. Defining the State

Given two strings $S1$ of length $M$ and $S2$ of length $N$, we define a 2D table dp[i][j] where:

i represents the first i characters of $S1$.
j represents the first j characters of $S2$.
dp[i][j] is the length of the LCS between $S1[0...i-1]$ and $S2[0...j-1]$.

2. The Recurrence Relation

When comparing $S1[i-1]$ and $S2[j-1]$:

If characters match ($S1[i-1] == S2[j-1]$):
- They must be part of the LCS.
- dp[i][j] = 1 + dp[i-1][j-1]
If characters do not match ($S1[i-1] != S2[j-1]$):
- The LCS is either the LCS of $S1[0..i-2]$ and $S2[0..j-1]$, OR the LCS of $S1[0..i-1]$ and $S2[0..j-2]$.
- dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. Complexity Analysis

Metric	Complexity	Description
Time	O(M * N)	Nested loops through both string lengths.
Space	O(M * N)	Full 2D table for results.
Space (Optimized)	O(min(M, N))	Since we only need the current and previous rows.

4. Implementation

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    let dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

5. Practical Applications

Diff Utilities: Tools like git diff use variations of LCS to determine which lines have changed between two versions of a file.
Bioinformatics: Comparing DNA sequences to find common genetic patterns.
Revision Control: Merging changes from multiple contributors.

Interview Pro-Tips: Subsequence vs. Substring

If an interviewer asks for the difference:

Substring: Must be contiguous (all characters next to each other in the original string).
Subsequence: Characters must be in the same order but can have "Gaps" between them.
Problem Strategy: Substring problems (like "Longest Common Substring") often use a slightly different DP recurrence where you reset the count to 0 if characters don't match.

Technical Summary

Subarray: Relies on matching characters and looking at the diagonal up-left.
O(MN): The standard DP complexity for two-string problems.
Base Cases: Initializing the first row and column with 0 (empty strings have 0 LCS).
Recovery: You can reconstruct the actual LCS string by backtracking from dp[m][n] based on whether characters matched or which direction the max came from.