Sequence DP#
Also known as: Subsequence DP, LIS / LCS Family, Two-String DP
Compare two sequences (or a sequence against itself) position by position, where each cell answers "the best I can do using the first i of one and the first j of the other." Match, and you extend a previous answer; mismatch, and you take the best of skipping one side or the other.
Before you start#
What 'solved properly' looks like
Target: O(n²) typically; LIS also has an O(n log n) form. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea#
You build a 2-D table where one sequence runs across the columns and the other down the rows. When the characters at (i, j) match, you extend the best answer from (i-1, j-1) by 1. When they don't match, you take the better of skipping one character from either sequence. The result in the bottom-right cell is the best you can do with the full sequences.
Why it matters: Edit distance powers spellcheck and diff tools. Longest increasing subsequence shows up disguised in scheduling and stacking problems. And the subsequence-versus-substring distinction — which this pattern makes unavoidable — is one of the most common conceptual traps in coding interviews.
When to reach for it#
Reach for it when you see "longest common subsequence", "longest increasing subsequence", "edit distance", or two strings being compared. Remember: a subsequence preserves order but allows gaps. Some contiguous-substring problems use sliding window, but when comparing two strings for a common substring, that's still Sequence DP — build the table and track the longest diagonal of matches.
When not to use it
A subsequence is not a substring. Substrings are contiguous, but that doesn't automatically make them sliding-window problems — longest common substring, for example, uses the same DP table as LCS, just tracking the longest diagonal of matches instead of allowing skips. Reaching for a window on a two-sequence comparison is a common wrong turn and produces answers that look nearly right. Also worth knowing: LIS has an O(n log n) solution built on binary search; the O(n²) DP is the one to understand, but not always the one to submit.
Practice set#
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Longest Common Subsequence | LeetCode | Medium | 25 mins | teaching |
| 2 | Longest Increasing Subsequence | LeetCode | Medium | 25 mins | teaching |
| 3 | Edit Distance | LeetCode | Medium | 30 mins | consolidation |
| 4 | Delete Operation for Two Strings | LeetCode | Medium | 25 mins | consolidation |
| 5 | Distinct Subsequences | LeetCode | Hard | 35 mins | challenge |
Already know this? Test out.
If you can solve Distinct Subsequences cleanly in one sitting — counting the number of distinct ways to form one string from another — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.