Longest Common Subsequence in DSA Typescript - Deep Dive

Overview - Longest Common Subsequence

What is it?

The Longest Common Subsequence (LCS) is a way to find the longest sequence of characters that appear in the same order in two strings, but not necessarily next to each other. It helps us understand how similar two sequences are by finding their shared pattern. For example, in the words 'ABCD' and 'ACBD', the LCS is 'ABD'.

Why it matters

LCS helps in many real-world problems like comparing DNA sequences in biology, finding differences between files in version control, and spell checking. Without LCS, it would be hard to measure similarity or changes between sequences, making tasks like merging documents or detecting plagiarism much more difficult.

Where it fits

Before learning LCS, you should understand basic strings and arrays, and simple loops. After LCS, you can explore more advanced dynamic programming problems like edit distance or sequence alignment.

Mental Model

Core Idea

The Longest Common Subsequence is the longest series of characters that appear in the same order in both sequences, even if they are not next to each other.

Think of it like...

Imagine two friends telling stories with some common events. The LCS is like the longest list of shared events they both mention in the same order, even if they skip some details.

  String1: A B C D G H
  String2: A E D F H R

  LCS path:
  A - - D - H

  Matrix example (partial):

    |   | A | E | D | F | H | R |
  --------------------------------
  |   | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  | A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
  | B | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
  | C | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
  | D | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
  | G | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
  | H | 0 | 1 | 1 | 2 | 2 | 3 | 3 |

Build-Up - 7 Steps

1

Foundation

Understanding subsequences and sequences

Concept: Learn what a subsequence is and how it differs from a substring or sequence.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, 'ACE' is a subsequence of 'ABCDE'. Unlike substrings, subsequences do not require characters to be next to each other.

Result

'ACE' is a subsequence of 'ABCDE', but 'AEC' is not because order matters.

Understanding subsequences is key because LCS finds the longest subsequence common to two sequences, not necessarily contiguous parts.

2

Foundation

Basic string comparison and matching

Concept: Learn how to compare characters of two strings one by one.

To find common parts, we compare characters from both strings. If characters match, they can be part of the subsequence. If not, we try skipping one character from either string and check again.

Result

Comparing 'A' and 'A' matches, but 'B' and 'E' do not.

Character-by-character comparison is the foundation for building the LCS solution.

3

Intermediate

Dynamic programming table setup

🤔Before reading on: do you think we can solve LCS by checking all subsequences directly or do we need a smarter way? Commit to your answer.

Concept: Use a table to store results of smaller problems to avoid repeated work.

We create a 2D table where rows represent characters of the first string and columns represent characters of the second string. Each cell stores the length of LCS for substrings up to those characters. We fill the table using rules: - If characters match, add 1 to diagonal cell value. - Else, take max from left or top cell.

Result

A filled table showing lengths of LCS for all substring pairs.

Using a table saves time by remembering past results, turning an exponential problem into a manageable one.

4

Intermediate

Reconstructing the LCS from the table

🤔Before reading on: do you think the LCS string is stored directly in the table or do we need to trace back? Commit to your answer.

Concept: After filling the table, we trace back from the bottom-right to find the actual LCS string.

Starting from the last cell, if characters match, add that character to the LCS and move diagonally up-left. If not, move in the direction of the larger neighboring cell (up or left). Continue until reaching the top or left edge.

Result

The LCS string reconstructed, e.g., 'ADH' for 'ABCDGH' and 'AEDFHR'.

Tracing back is necessary because the table only stores lengths, not the subsequence itself.

5

Intermediate

Implementing LCS in TypeScript

🤔Before reading on: do you think the implementation will be recursive or iterative? Commit to your answer.

Concept: Write a TypeScript function using dynamic programming to compute LCS length and sequence.

We create a 2D array dp of size (m+1) x (n+1) where m and n are string lengths. Fill dp iteratively using the rules: - If s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1] + 1 - Else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) Then reconstruct LCS by tracing back. Example code: function longestCommonSubsequence(s1: string, s2: string): string { const m = s1.length, n = s2.length; const dp: number[][] = Array.from({ length: m + 1 }, () => 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]); } } } let i = m, j = n; let lcs = ''; while (i > 0 && j > 0) { if (s1[i - 1] === s2[j - 1]) { lcs = s1[i - 1] + lcs; i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } return lcs; }

Result

For inputs 'ABCDGH' and 'AEDFHR', output is 'ADH'.

Implementing LCS with dynamic programming in code shows how theory turns into practical solutions.

6

Advanced

Optimizing space complexity

🤔Before reading on: do you think we need to keep the entire dp table to find LCS length? Commit to your answer.

Concept: Reduce memory use by storing only necessary rows during computation.

Since each dp row depends only on the previous row, we can keep two 1D arrays instead of a full 2D table. This reduces space from O(m*n) to O(min(m,n)). However, reconstructing the LCS string requires extra care or a different approach.

Result

Memory usage drops significantly while still computing LCS length correctly.

Knowing how to optimize space is crucial for large inputs and real-world efficiency.

7

Expert

LCS variations and real-world surprises

🤔Before reading on: do you think LCS always finds the most meaningful similarity? Commit to your answer.

Concept: Explore variations like weighted LCS, and understand limitations in practical applications.

In some cases, not all characters have equal importance. Weighted LCS assigns scores to characters. Also, LCS does not consider character substitutions or rearrangements, which limits its use in some fields. Advanced algorithms like edit distance or sequence alignment handle these cases better.

Result

Awareness of LCS limits and when to choose other algorithms.

Understanding LCS limitations prevents misuse and guides choosing the right tool for complex similarity problems.

Under the Hood

LCS uses dynamic programming to break the problem into smaller overlapping subproblems. It builds a table where each cell represents the LCS length for prefixes of the two strings. The algorithm compares characters and uses previously computed results to avoid redundant calculations, making it efficient.

Why designed this way?

The problem of finding common subsequences has many overlapping subproblems, which naive recursion would solve repeatedly, causing exponential time. Dynamic programming was designed to store these results and reuse them, drastically improving performance from exponential to polynomial time.

┌─────────────┬─────┬─────┬─────┬─────┐
│             │ ''  │ A   │ B   │ C   │
├─────────────┼─────┼─────┼─────┼─────┤
│ ''          │ 0   │ 0   │ 0   │ 0   │
│ A           │ 0   │ 1   │ 1   │ 1   │
│ C           │ 0   │ 1   │ 1   │ 2   │
│ B           │ 0   │ 1   │ 2   │ 2   │
└─────────────┴─────┴─────┴─────┴─────┘

Each cell dp[i][j] = max LCS length for s1[0..i-1], s2[0..j-1].

Myth Busters - 4 Common Misconceptions

Quick: Does LCS require characters to be next to each other in both strings? Commit yes or no.

Common Belief: LCS finds the longest common substring, so characters must be consecutive.

Reality: LCS finds the longest common subsequence, which does not require characters to be consecutive, only in order.

Why it matters: Confusing substring with subsequence leads to wrong algorithms and incorrect results.

Quick: Is the LCS always unique for two given strings? Commit yes or no.

Common Belief: There is only one longest common subsequence for any two strings.

Reality: Multiple different subsequences can have the same maximum length.

Why it matters: Assuming uniqueness can cause bugs when reconstructing or comparing LCS results.

Quick: Does LCS handle character substitutions or rearrangements? Commit yes or no.

Common Belief: LCS accounts for substitutions and rearrangements to find similarity.

Reality: LCS only finds common subsequences; it does not handle substitutions or rearrangements.

Why it matters: Using LCS for problems needing substitutions (like spell check) leads to poor results; edit distance is better.

Quick: Can we solve LCS efficiently without dynamic programming? Commit yes or no.

Common Belief: A simple recursive solution without memoization is efficient enough for large inputs.

Reality: Naive recursion is exponential and impractical for large inputs; dynamic programming is necessary.

Why it matters: Ignoring dynamic programming causes slow programs and timeouts in real applications.

Expert Zone

1

The order of strings affects space optimization; always use the shorter string for the dp array to save memory.

2

Reconstructing the LCS string from a space-optimized dp array requires additional techniques like Hirschberg's algorithm.

3

Weighted or generalized LCS can incorporate character importance or multiple sequences, but increase complexity.

When NOT to use

Avoid LCS when you need to consider character substitutions, insertions, or deletions with costs; use edit distance or sequence alignment algorithms instead.

Production Patterns

LCS is used in diff tools to highlight changes between file versions, in bioinformatics for DNA sequence comparison, and in text comparison tools to detect plagiarism or similarity.

Connections

Edit Distance

Builds on and extends LCS by considering substitutions, insertions, and deletions with costs.

Understanding LCS helps grasp edit distance since LCS length relates directly to minimum edits needed.

Dynamic Programming

LCS is a classic example of dynamic programming solving overlapping subproblems efficiently.

Mastering LCS strengthens understanding of dynamic programming principles applicable to many problems.

Genetic Sequence Alignment (Bioinformatics)

LCS is a simplified form of sequence alignment used to find common patterns in DNA or proteins.

Knowing LCS helps appreciate how biological data is compared and analyzed computationally.

Common Pitfalls

#1 Trying to find LCS by checking all subsequences directly.

Wrong approach:

function lcsNaive(s1: string, s2: string): number {
// Generate all subsequences of s1 and check if in s2
// Exponential time, impractical
return 0; // placeholder
}

Correct approach:

Use dynamic programming with a 2D dp array to store intermediate results and build up the solution efficiently.

Root cause:

Not realizing the exponential number of subsequences and the need for memoization or tabulation.

#2 Confusing substring with subsequence and expecting consecutive matches.

Wrong approach:

Assuming LCS requires characters to be next to each other and stopping search early.

Correct approach:

Allow skipping characters and only require order to be maintained, enabling non-contiguous matches.

Root cause:

Misunderstanding the definition of subsequence versus substring.

#3 Reconstructing LCS string incorrectly by reading dp table from top-left to bottom-right.

Wrong approach:

for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dp[i][j] > 0) lcs += s1[i];
}
}

Correct approach:

Trace back from dp[m][n] to dp[0][0], moving diagonally when characters match, or up/left otherwise.

Root cause:

Not understanding that dp table stores lengths, not the subsequence itself.

Key Takeaways

Longest Common Subsequence finds the longest ordered sequence shared by two strings without requiring characters to be next to each other.

Dynamic programming transforms the LCS problem from exponential to polynomial time by storing results of smaller problems.

Reconstructing the actual LCS requires tracing back through the dynamic programming table, not just reading values.

Space optimization techniques reduce memory use but complicate reconstruction, requiring advanced methods.

LCS has limits and does not handle substitutions or rearrangements; other algorithms like edit distance are needed for those cases.

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