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.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The total number of characters in both strings combined

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

C. The shortest sequence of characters to convert one string into another

D. The longest substring that appears in both strings consecutively

Solution

1. Step 1: Understand the definition of LCS

   The LCS is the longest sequence that appears in both strings in the same order but not necessarily next to each other.

2. Step 2: Differentiate from substring and edit distance

   Unlike substring, LCS does not require characters to be consecutive. It is not about shortest edits either.

3. Final Answer:

   The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively -> Option B

4. Quick Check:

   LCS means longest common sequence, not substring or edits [OK]

Hint: LCS is about order, not consecutive characters [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking LCS requires consecutive characters
• Mixing LCS with edit distance or shortest transformation

2. Which of the following TypeScript function signatures correctly represents a function to compute LCS length between two strings s1 and s2?

easy

A. function lcsLength(s1: string, s2: string): string[]

B. function lcsLength(s1: number[], s2: number[]): string

C. function lcsLength(s1: string, s2: string): void

D. function lcsLength(s1: string, s2: string): number

Solution

1. Step 1: Identify input and output types for LCS length

   The function takes two strings and returns a number representing the length of their LCS.

2. Step 2: Check each option's signature

   function lcsLength(s1: string, s2: string): number matches input strings and returns a number. Others either use wrong input types or return wrong types.

3. Final Answer:

   function lcsLength(s1: string, s2: string): number -> Option D

4. Quick Check:

   Input strings, output number for LCS length [OK]

Hint: LCS length function returns a number, inputs are strings [OK]

Common Mistakes:

• Using arrays instead of strings as input
• Returning string or void instead of number
• Confusing LCS length with LCS sequence output

3. What is the output of the following TypeScript code snippet?

function lcsLength(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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];
}

console.log(lcsLength('AGGTAB', 'GXTXAYB'))

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Understand the LCS dynamic programming table

   The code builds a 2D table dp where dp[i][j] stores LCS length of s1[0..i-1] and s2[0..j-1].

2. Step 2: Trace LCS for 'AGGTAB' and 'GXTXAYB'

   The LCS is 'GTAB' with length 4, but careful tracing shows length 4 is correct. However, the known LCS length for these strings is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   LCS('AGGTAB','GXTXAYB') = 4 [OK]

Hint: Trace dp table or recall classic example LCS length 4 [OK]

Common Mistakes:

• Confusing LCS length with substring length
• Miscounting matching characters
• Off-by-one errors in indexing

4. Identify the bug in the following TypeScript code that attempts to compute the LCS length:

function lcsLength(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array(m).fill(Array(n).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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 - 1][n - 1];
}

medium

A. dp array initialization shares inner arrays causing incorrect updates

B. Loop indices should start from 0 instead of 1

C. Return statement should be dp[m][n] instead of dp[m - 1][n - 1]

D. Comparison should be s1[i] === s2[j] instead of s1[i - 1] === s2[j - 1]

Solution

1. Step 1: Analyze dp array initialization

   Using Array(m).fill(Array(n).fill(0)) creates m references to the same inner array, causing shared rows.

2. Step 2: Understand impact on dp updates

   Updating dp[i][j] affects all rows because they point to the same array, corrupting the dp table.

3. Final Answer:

   dp array initialization shares inner arrays causing incorrect updates -> Option A

4. Quick Check:

   Array fill with same inner array causes shared references [OK]

Hint: Use map to create independent inner arrays for dp [OK]

Common Mistakes:

• Using fill with array causes shared references
• Incorrect dp return indices
• Off-by-one errors in loops

5. Given two strings s1 = 'ABCBDAB' and s2 = 'BDCABA', which of the following is a valid Longest Common Subsequence?

hard

A. 'BDCA'

B. 'BCBD'

C. 'BDAB'

D. 'BDA'

Solution

1. Step 1: Determine length of LCS

   The LCS length for these strings is 4.

2. Step 2: Check each option for validity and length

   'BDAB' is length 4 and appears in order in both strings. Others are either shorter or invalid sequences.

3. Final Answer:

   'BDAB' -> Option C

4. Quick Check:

   Valid LCS must be subsequence and max length 4 [OK]

Hint: Check subsequence order and length equals LCS length [OK]

Common Mistakes:

• Choosing subsequences not in order in both strings
• Picking shorter subsequences ignoring max length
• Confusing substring with subsequence