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].