Longest Common Subsequence in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Subsequence (LCS)?

LCS is the longest sequence that appears in the same relative order in two sequences, but not necessarily contiguously.

intermediate

How does dynamic programming help in finding LCS?

It breaks the problem into smaller overlapping subproblems and stores their results to avoid repeated work, building up the solution efficiently.

intermediate

What does the DP table represent in LCS algorithm?

Each cell dp[i][j] stores the length of LCS of the first i characters of string A and first j characters of string B.

beginner

In LCS, what happens when characters at current indices match?

We add 1 to the LCS length found by excluding these characters, i.e., dp[i][j] = 1 + dp[i-1][j-1].

intermediate

What is the time complexity of the classic LCS dynamic programming solution?

It is O(m * n), where m and n are the lengths of the two input sequences.

What does LCS stand for?

A Least Common Substring

B Largest Common Substring

C Longest Continuous Sequence

D Longest Common Subsequence

LCS stands for Longest Common Subsequence, which is a sequence appearing in the same order in both strings.

If characters at current indices of both strings match, what is the LCS relation?

A dp[i][j] = 1 + dp[i-1][j-1]

B dp[i][j] = max(dp[i-1][j], dp[i][j-1])

C dp[i][j] = dp[i-1][j-1]

D dp[i][j] = 0

When characters match, we add 1 to the LCS length found by excluding these characters.

What is stored in dp[i][j] in the LCS DP table?

A Length of LCS of first i characters of string A and first j characters of string B

B Length of longest substring ending at i and j

C Number of matching characters at i and j

D Sum of ASCII values of matched characters

dp[i][j] stores the length of the longest common subsequence of the first i characters of string A and first j characters of string B.

What is the time complexity of the classic LCS algorithm using DP?

A O(m + n)

B O(m * n)

C O(m^2 + n^2)

D O(2^(m+n))

The classic DP solution for LCS runs in O(m * n) time, where m and n are the lengths of the two strings.

If characters at current indices do not match, how is dp[i][j] computed?

A dp[i][j] = dp[i-1][j-1]

B dp[i][j] = 1 + dp[i-1][j-1]

C dp[i][j] = max(dp[i-1][j], dp[i][j-1])

D dp[i][j] = 0

If characters don't match, dp[i][j] is the maximum LCS length by excluding one character from either string.

Explain how the dynamic programming table is built for the Longest Common Subsequence problem.

Think about how smaller problems help solve bigger ones step by step.

Describe the difference between Longest Common Subsequence and Longest Common Substring.

One cares about order, the other about continuous matching.

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