Longest Common Subsequence (LCS)

@lcs

The Longest Common Subsequence (LCS) finds the longest sequence of characters that appear in the same order in both sequences (not necessarily next to each other).

Pseudo-code
function LCS(A, B):

  m = length(A)
  n = length(B)

  # Step 1: Create DP table
  L = 2D array of size (m+1) x (n+1)

  # Step 2: Fill table
  for i from 0 to m:
    for j from 0 to n:

      # Base case
      if i == 0 or j == 0:
        L[i][j] = 0

      # Characters match
      else if A[i-1] == B[j-1]:
        L[i][j] = L[i-1][j-1] + 1

      # Characters do not match
      else:
        L[i][j] = max(L[i-1][j], L[i][j-1])

  return L[m][n]
  • A The first sequence (like a string or list).
  • B The second sequence.
  • m The length of A.
  • n The length of B.
  • L A 2D table where L[i][j] stores the length of the LCS of A[0..i-1] and B[0..j-1].
  • i Row index (used for sequence A).
  • j Column index (used for sequence B).
  • x Temporary variable sometimes used to store max values during computation.
  • 0 Base value used when one sequence is empty.
Recipe Steps
1

Think of matching letters — You have two words and want the longest matching pattern in order.

2

Create a grid — Rows for A, columns for B.

3

Fill the first row and column with 0 because empty strings have no matches.

4

If letters match, take the diagonal value and add 1.

5

If they do not match, take the maximum from left or top.

6

Repeat until the grid is filled.

7

The bottom-right value is the length of the longest common subsequence.

Questions & Answers

A sequence that keeps the same order but may skip elements.

We take the diagonal value and add 1.

We take the maximum of top or left.

Yes, because the order is preserved.
- Time complexity is O(m * n).
- Used in DNA matching, diff tools, and text comparison.
- Tip: Think of it as building answers for smaller prefixes.
- Common mistake: Confusing subsequence with substring (substring must be continuous).
- You can reconstruct the actual sequence by backtracking through the table.

Related Algorithms
Decision Tree (ID3 / CART)

A Decision Tree builds a flowchart-like structure that splits data step by step using features, until it can make a clear prediction.

View
Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes by gradually improving paths using intermediate nodes.

View
Gradient Descent

Gradient Descent is a way for machines to learn from data by adjusting their predictions to get closer to the correct answer. It's like a never-ending staircase where the machine takes small steps down until it reaches the bottom, which is the optimal solution.

View