Longest Common Subsequence in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D array for dynamic programming.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Am + 1

Bn + 1

Cn

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using m instead of n for the inner array size.

Not adding 1 to the lengths for dp array size.

The dp array has dimensions (m+1) x (n+1) to cover all prefixes of both strings.

2fill in blank

medium

Complete the code to check if characters match at current indices.

DSA Typescript

if (text1[i - 1] [1] text2[j - 1]) {

Drag options to blanks, or click blank then click option'

A==

B!=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality instead of equality.

Using greater than or less than operators.

We check if characters at positions i-1 and j-1 are equal to extend the subsequence.

3fill in blank

hard

Fix the error in updating dp when characters do not match.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Aj - 1

Bi - 1

Cj + 1

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i-1 instead of j-1 for the second index.

Using j+1 or i+1 which goes out of bounds.

When characters don't match, dp[i][j] is max of dp[i-1][j] and dp[i][j-1].

4fill in blank

hard

Fill both blanks to complete the nested loops iterating over dp table.

DSA Typescript

for (let i = 1; i [1] m + 1; i++) {
  for (let j = 1; j [2] n + 1; j++) {

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes index out of bounds.

Using > or >= reverses loop logic.

Loops run from 1 up to but not including m+1 and n+1, so use '<' operator.

5fill in blank

hard

Fill all three blanks to return the final LCS length from dp table.

DSA Typescript

return dp[1][2][3];

Drag options to blanks, or click blank then click option'

A[m]

B[n]

C[n][m]

D[m][n]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[n][m] which swaps indices.

Using dp[m] or dp[n] which returns a row or column, not a single value.

The LCS length is stored at dp[m][n], the bottom-right cell of the dp table.

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