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

Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Ready

String 1

String 2

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

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) \times (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".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep