Longest Common Subsequence in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCS length calculation

What is the output of the following TypeScript code that calculates the length of the Longest Common Subsequence (LCS) between two strings?

DSA Typescript

function lcsLength(a: string, b: string): number {
  const m = a.length, n = b.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 (a[i - 1] === b[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"));

A 5

B 3

C 6

D 4

💡 Hint

Trace the matching characters and count the longest sequence common to both strings.

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB" which has length 4. The code correctly computes and returns 4.

❓ Predict Output

intermediate

Output of LCS sequence reconstruction

What is the output of the following TypeScript code that reconstructs the Longest Common Subsequence (LCS) string between two inputs?

DSA Typescript

function lcsSequence(a: string, b: string): string {
  const m = a.length, n = b.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 (a[i - 1] === b[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]);
      }
    }
  }
  let i = m, j = n;
  let lcs = '';
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      lcs = a[i - 1] + lcs;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}

console.log(lcsSequence("ABCBDAB", "BDCABA"));

A "BCAB"

B "BDAB"

C "BDCB"

D "BCBA"

💡 Hint

Follow the dp table backwards to build the LCS string.

The longest common subsequence between "ABCBDAB" and "BDCABA" is "BCAB" which is correctly reconstructed by the code.

🔧 Debug

advanced

Identify the error in LCS length code

What error will the following TypeScript code produce when trying to calculate the LCS length?

DSA Typescript

function lcsLength(a: string, b: string): number {
  const m = a.length, n = b.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 (a[i - 1] === b[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];
}

console.log(lcsLength("ABC", "AC"));

A No error, returns correct length 2

B IndexError: list index out of range

C TypeError: Cannot set property '1' of undefined

D Returns incorrect LCS length 1

💡 Hint

Check how the dp array is initialized and accessed.

The dp array is created with Array(m) which has indices 0 to m-1, but the loop goes to i <= m accessing dp[m] which is undefined, causing a TypeError on assignment. Additionally, using fill with the same inner array shares references across rows.

🧠 Conceptual

advanced

Time complexity of LCS dynamic programming

What is the time complexity of the classic dynamic programming solution to find the length of the Longest Common Subsequence of two strings of lengths m and n?

A O(m + n)

B O(m * n)

C O(m^2 + n^2)

D O(2^(m + n))

💡 Hint

Consider the nested loops over both strings.

The DP solution fills a 2D table of size (m+1) by (n+1), with two nested loops, so O(m * n) time.

🚀 Application

expert

Longest Common Subsequence count of distinct subsequences

Given two strings, how many distinct longest common subsequences can they have? For example, for strings "ABCBDAB" and "BDCABA", how many distinct LCS strings exist?

A 3

B 2

C 1

D 4

💡 Hint

There can be multiple LCS strings of the same maximum length.

For the example strings, there are 3 distinct LCS strings of length 4: "BCAB", "BDAB", and "BCBA".