Subsequence vs Substring?

A Subsequence does not require elements to be contiguous (only in order). A Substring MUST be contiguous.

LCS transition formula?

If characters match: 1 + dp[i-1][j-1]. If no match: max(dp[i-1][j], dp[i][j-1]).

Real-world uses of LCS?

Git "diff" commands, DNA sequence alignment, and spell checkers often use variations of LCS.

Longest Common Subsequence

The longest common subsequence (LCS) of two strings is the longest sequence that appears in both in the same order. A subsequence is derived from another sequence by deleting some or no elements without changing the order of the rest.

READY

Initialize DP table of size (6x4) with 0s.

Comparing 'A' (Row 1) and 'A' (Col 1)

String 1

String 2

Intuition

Imagine comparing two files line by line to find differences. You want to match as many lines as possible in the same relative order. If two characters match, great! If not, you have to decide whether to skip a character from the first string or the second string to find the next match.

Concept

2D Dynamic Programming:

We define dp[i][j] as the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.

Recurrence Relation:

Match (text1[i] == text2[j]): 1 + dp[i-1][j-1] (extend the best result without these characters).
Mismatch (text1[i] != text2[j]): max(dp[i-1][j], dp[i][j-1]) (keep the best result by skipping one character).

How it Works

Tabulation Algorithm:

Initialize a table dp of size (m+1) × (n+1) with 0s.
Iterate i from 1 to m (text1).
Iterate j from 1 to n (text2).
If characters match, look diagonally up-left and add 1.
If mismatch, look left and up, take the maximum.
The value dp[m][n] is the answer.

Step-by-Step Breakdown

Visualizing the table:

Diagonal Arrow: Indicates a match (extend subsequence).
Left/Up Arrow: Indicates carrying forward the best previous result during a mismatch.
Path Reconstruction: Backtracking from bottom-right to top-left gives the actual string.

When to Use

Applications:

File matching (diff utilities).
Bioinformatics (DNA sequence alignment).
Spell checking (fuzzy matching).

When NOT to Use

Contiguous Substrings: If the match must be contiguous, the recurrence changes (reset to 0 on mismatch).
Permutations: If order doesn't matter at all, use frequency counts.

How to Identify

"Common subsequence", "Pattern matching with deletions", "Sequence alignment".

Sample Problems

Shortest Common Supersequence

Construct the shortest string containing both as subsequences.

Distinct Subsequences

Count ways to form a subsequence.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Subset Sum

Longest Increasing Subsequence