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.