Longest Common Subsequence in DSA Typescript - Build from Scratch

Longest Common Subsequence

📖 Scenario: You are working on a text comparison tool that helps find similarities between two strings. One important feature is to find the longest common subsequence (LCS) between two given strings. This helps in understanding how much two texts have in common, even if some characters are skipped.

🎯 Goal: Build a TypeScript program that calculates the length of the longest common subsequence between two strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D array to store intermediate LCS lengths

Use nested loops to fill the 2D array based on LCS logic

Print the final LCS length

💡 Why This Matters

🌍 Real World

Finding longest common subsequence is useful in text comparison tools, DNA sequence analysis, and version control systems to detect similarities.

💼 Career

Understanding dynamic programming and string algorithms is important for software engineers working on data processing, bioinformatics, and software development involving text or sequence analysis.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "AGGTAB" and "GXTXAYB" respectively.

DSA Typescript

# Your code here
// Create two strings str1 and str2 with given values

Hint

Use const to declare the strings exactly as given.

2

Initialize the 2D array for LCS lengths

Create a 2D array called dp with dimensions (str1.length + 1) by (str2.length + 1). Initialize all values to 0.

DSA Typescript

const str1: string = "AGGTAB";
const str2: string = "GXTXAYB";
// Create a 2D array dp with zeros
// Your code here

Hint

Use Array(length).fill(null).map(() => Array(...).fill(0)) to create a 2D array filled with zeros.

3

Fill the 2D array using LCS logic

Use nested for loops with variables i from 1 to str1.length and j from 1 to str2.length. Inside the loops, if str1[i - 1] equals str2[j - 1], set dp[i][j] = dp[i - 1][j - 1] + 1. Otherwise, set dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]).

DSA Typescript

const str1: string = "AGGTAB";
const str2: string = "GXTXAYB";

const dp: number[][] = Array(str1.length + 1).fill(null).map(() => Array(str2.length + 1).fill(0));

// Fill dp using nested loops and LCS logic
// Your code here

Hint

Use two nested loops and compare characters at i - 1 and j - 1 positions.

4

Print the length of the longest common subsequence

Print the value of dp[str1.length][str2.length] using console.log.

DSA Typescript

const str1: string = "AGGTAB";
const str2: string = "GXTXAYB";

const dp: number[][] = Array(str1.length + 1).fill(null).map(() => Array(str2.length + 1).fill(0));

for (let i = 1; i <= str1.length; i++) {
    for (let j = 1; j <= str2.length; j++) {
        if (str1[i - 1] === str2[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]);
        }
    }
}

// Print the final LCS length
// Your code here

Hint

The longest common subsequence length is stored at dp[str1.length][str2.length].

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