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.