Longest Common Subsequence in DSA Typescript

Mental Model

Find the longest sequence of characters that appear in the same order in both strings, but not necessarily consecutively.

Analogy: Imagine two friends telling stories with some common events. The longest common subsequence is like the longest list of shared events they both mention in the same order, even if they skip some details.

String1: A B C D G H
String2: A E D F H R

LCS path:
A ->   -> D ->   -> H

Positions:
String1: [A][B][C][D][G][H]
          ↑           ↑     ↑
String2: [A][E][D][F][H][R]
          ↑     ↑           ↑

Dry Run Walkthrough

Input: string1: "ABCDGH", string2: "AEDFHR"

Goal: Find the longest common subsequence between the two strings.

Step 1: Initialize a 2D array dp with dimensions (7 x 7) filled with zeros (lengths of strings + 1).

dp matrix filled with zeros:
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]

Why: We need a table to store lengths of LCS for substrings to build up the solution.

Step 2: Compare characters at positions i=1 (A) and j=1 (A), they match, so dp[1][1] = dp[0][0] + 1 = 1.

dp[1][1] = 1
Partial dp:
[0,0,0,0,0,0,0]
[0,1,0,0,0,0,0]
...

Why: Matching characters add 1 to the LCS length from previous substrings.

Step 3: Compare i=2 (B) and j=2 (E), no match, so dp[2][2] = max(dp[1][2], dp[2][1]) = max(0,1) = 1.

dp[2][2] = 1
Partial dp:
[0,0,0,0,0,0,0]
[0,1,0,0,0,0,0]
[0,1,1,0,0,0,0]
...

Why: No match means we take the best LCS length from previous substrings.

Step 4: Compare i=4 (D) and j=3 (D), match found, dp[4][3] = dp[3][2] + 1 = 2.

dp[4][3] = 2
Partial dp:
...
[0,1,1,2,...]
...

Why: Matching characters increase LCS length by 1 from previous substrings.

Step 5: Fill the rest of dp table by comparing all characters and taking max or adding 1 on match.

Final dp matrix:
[0,0,0,0,0,0,0]
[0,1,1,1,1,1,1]
[0,1,1,1,1,1,1]
[0,1,1,1,1,1,1]
[0,1,1,2,2,2,2]
[0,1,1,2,2,2,2]
[0,1,1,2,2,3,3]

Why: Complete dp table gives lengths of LCS for all substring pairs.

Step 6: Trace back from dp[6][6] to find the LCS string by moving diagonally on matches or up/left on max values.

LCS found: A D H

Why: Backtracking reconstructs the actual longest common subsequence.

Result:

Final LCS length = 3
LCS string = "ADH"

Annotated Code

DSA Typescript

class LongestCommonSubsequence {
  static lcs(str1: string, str2: string): string {
    const m = str1.length;
    const n = str2.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // Build dp table
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (str1[i - 1] === str2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1; // match found, extend LCS
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match, take max
        }
      }
    }

    // Backtrack to find LCS string
    let i = m, j = n;
    let lcsStr = '';
    while (i > 0 && j > 0) {
      if (str1[i - 1] === str2[j - 1]) {
        lcsStr = str1[i - 1] + lcsStr; // add matching char
        i--;
        j--;
      } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--; // move up
      } else {
        j--; // move left
      }
    }

    return lcsStr;
  }
}

// Driver code
const str1 = "ABCDGH";
const str2 = "AEDFHR";
const result = LongestCommonSubsequence.lcs(str1, str2);
console.log(result);

if (str1[i - 1] === str2[j - 1]) {

Check if current characters match to extend LCS length

dp[i][j] = dp[i - 1][j - 1] + 1;

On match, increase LCS length by 1 from previous substrings

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

On no match, take max LCS length from skipping one character

while (i > 0 && j > 0) {

Backtrack through dp table to reconstruct LCS string

if (str1[i - 1] === str2[j - 1]) {

If characters match, add to LCS and move diagonally

else if (dp[i - 1][j] > dp[i][j - 1]) {

Move up if dp value above is greater

else { j--; }

Move left if dp value left is greater or equal

Output

ADH

Complexity Analysis

Time: O(m*n) because we fill a 2D table of size m by n once

Space: O(m*n) because we store LCS lengths for all substring pairs in a 2D array

vs Alternative: Naive recursive approach is exponential O(2^(m+n)) due to repeated subproblems; DP reduces it to polynomial time

Edge Cases

One or both strings are empty

LCS length is zero and result is empty string

DSA Typescript

const m = str1.length; const n = str2.length; (dp initialized with zeros)

Strings have no common characters

LCS length is zero and result is empty string

DSA Typescript

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

Strings are identical

LCS is the entire string

DSA Typescript

if (str1[i - 1] === str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; }

When to Use This Pattern

When asked to find the longest sequence common to two sequences in order but not necessarily contiguous, use the Longest Common Subsequence pattern with dynamic programming.

Common Mistakes

Mistake: Not initializing the dp array with zeros causing undefined values
Fix: Initialize dp with zeros for all indices before filling

Mistake: Incorrectly indexing strings causing off-by-one errors
Fix: Use i-1 and j-1 to access string characters when dp indices start at 1

Mistake: Not backtracking correctly to reconstruct the LCS string
Fix: Follow dp table from bottom-right, moving diagonally on match, up or left otherwise

Summary

Finds the longest sequence of characters common to two strings in order.

Use when you need to compare two sequences and find their longest shared pattern.

The key is building a table of solutions for smaller substrings and combining them.