Two families, one shape. On strings, the second index becomes a position in a second string: if the characters match, take them both and step back together; if not, try dropping one from each side and keep the better. On stocks, the second index becomes a flag you carry — am I holding, and how many transactions are left. Sixteen lectures, and both families are pick / not-pick with a wider state.
This is not a list of problems. It is 16 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDDecks I and II of this step. Every string problem here is pick / not-pick with TWO indices instead of one; every stock problem is pick / not-pick with a flag you carry. Nothing new is added to the method.
16 PROBLEMS · EVERY ONE LINKS TO A JUDGE TO SOLVE
Ten of these rows put a second STRING on the other index; six put a small carried STATE there instead. Both are pick / not-pick with a wider state, and the phrasing of the statement is what tells you which table you are about to fill.
one index per string; a match is free to take, a mismatch means try dropping either
LCS TABLE · the parent of every string row hereO(n·m)a mismatch breaks the run, so the cell resets to 0 rather than inheriting a neighbour
SUBSTRING · answer is the largest cell, not the cornerO(n·m)a palindrome reads the same reversed, so it is common to s and reverse(s)
REVERSE AND REUSE · LCS(s, reverse s)O(n²)whatever is common survives; everything else is deleted from one side and inserted into the other
n + m − 2·LCS · arithmetic, not a new tableO(n·m)the transition is dictated by the characters, and a match may not be forced
MATCHING DP · add the branches, or OR themO(n·m)the day is the index; whether you hold, and how many trades remain, is the carried state
STOCK DP · state = (day, holding, cap)O(n·k)A pairwise string table costs n·m cells. That is the number to check first: two strings of 10³ is a million cells and fine, two of 10⁵ is 10¹⁰ and impossible — and when it is impossible the answer is not a better DP, it is a different technique.
The stock rows are the exception in this deck: one string, one flag, and O(n) — which is why they can take n = 10⁵ where the string rows cannot.
An LCS table over strings of length n and m is built with dimensions (n+1) × (m+1). What is the extra row and column for?
Row 0 means 'no characters of a yet', and its LCS with anything is genuinely 0. So the base case IS the extra row, and the recurrence can read i−1 everywhere without a single guard. This is why the tabulated version shifts to 1-based indexing even though the strings are 0-based.
Two characters MATCH while filling an LCS table. Why is it safe to take the pair rather than considering skipping it?
An exchange argument. Any common subsequence not using this pair can be rewritten to use it without getting shorter, so there is nothing to lose. That certainty is what makes LCS a two-branch table rather than a three-branch one — and note that Distinct Subsequences, later, is the one place it fails.
Edit distance. It compiles and returns a plausible number that is always too large. Which line?
int f(int i, int j, string& a, string& b, vector<vector<int>>& dp){ if(i == 0) return j; if(j == 0) return i; if(dp[i][j] != -1) return dp[i][j]; if(a[i-1] == b[j-1]) return dp[i][j] = 1 + f(i-1, j-1, a, b, dp); return dp[i][j] = 1 + min({f(i, j-1, a, b, dp), f(i-1, j, a, b, dp), f(i-1, j-1, a, b, dp)}); }
A match is free. Charging 1 for it inflates the answer by exactly the length of the common subsequence — a number that scales sensibly with the input, never crashes, and looks entirely reasonable until you check a small case by hand. That is what makes it expensive.
A stock problem tracks whether you currently hold a share. Why is that a better state than remembering the price you bought at?
State size is the whole game. A boolean gives 2n cells; a remembered price gives n² and puts a 10⁵-day problem out of reach. The profit already accounts for what you paid, so the price does not need remembering — recognising what can be dropped from a state is the skill this section drills.
Sixteen lectures, 6h 07m, and for the only time in the playlist sixteen lectures against sixteen sheet rows — no lecture without a row, no row without a lecture. Units 01 to 07 are one table read seven ways; 08 to 10 change what a match MEANS; 11 to 16 drop to a single string and grow a carried state instead.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Two indices, one per string — the table every string row here reuses
WHAT IS THE LONGEST SEQUENCE OF CHARACTERS THESE TWO STRINGS SHARE, IN ORDER?
The lecture opens by counting subsequences of a length-n string. How many are there?
Each character is independently in or out, so 2ⁿ — the same pick / not-pick that deck II ran on numbers, now on characters. It is also why brute force is hopeless and why the table has to exist.
Characters at i and j MATCH. What does the transition do?
A matching pair can always be taken — no better answer ever skips it — so you bank the 1 and shrink both strings. That certainty is what makes this an O(n·m) table rather than a search.
Characters DON'T match. What happens?
max(f(i−1, j), f(i, j−1)). You cannot know which character to discard, so you try both and keep whichever leads further. Two branches per cell, exactly as in decks I and II.
The tabulated version shifts to 1-based indexing. Why is that worth the confusion?
The recurrence reads i−1 and j−1, which at index 0 would be −1. Shifting by one turns that into row 0 meaning 'empty string', which is genuinely 0 — so the base case IS the extra row, and no guard is needed anywhere.
abcde against ace. Row and column 0 are the EMPTY prefix, which is why the table is one larger than the strings and why i-1 never needs a guard. Characters match → bank one and step diagonally; they do not → drop one from each side and keep the better. Watch which cells each answer reads.
Two strings and the words “longest common”. One index per string, and the answer is a length rather than a string — which is what makes it a table and not a search.
Compare the last characters. If they match, that pair can always be taken — no answer is made worse by banking it — so add one and shrink both strings. If they do not, you cannot know which to discard, so try both and keep the better. The table is one larger than the strings so that row 0 means 'the empty prefix', which is genuinely 0 and removes every bounds check.
int lcs(string& a, string& b) { int n = a.size(), m = b.size(); vector<int> prev(m + 1, 0), cur(m + 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i-1] == b[j-1]) cur[j] = 1 + prev[j-1]; // bank the match else cur[j] = max(prev[j], cur[j-1]); } prev = cur; } return prev[m]; }
def lcs(a, b): m = len(b) prev = [0] * (m + 1) for i in range(1, len(a) + 1): cur = [0] * (m + 1) for j in range(1, m + 1): if a[i-1] == b[j-1]: cur[j] = 1 + prev[j-1] # bank the match else: cur[j] = max(prev[j], cur[j-1]) prev = cur return prev[m]
Indexing the strings with i and j rather than i−1 and j−1 after the 1-based shift. The table is 1-indexed and the strings are not, and mixing them reads the wrong characters — producing a smaller answer on most inputs and the right one on a few.
Reading a string back out of a table that only stored numbers
THE TABLE GIVES THE LENGTH. HOW DO YOU RECOVER THE ACTUAL SUBSEQUENCE?
To recover the actual subsequence rather than its length, what do you do?
The table already contains the answer — you just have to read it. Storing strings in cells costs O(n·m·length) memory for information the numbers already imply. Reconstruction by walking back is the general technique, not an LCS trick.
During the backward walk you are at (i, j) and the characters DON'T match. Where do you go?
You retrace the choice the fill made, and the fill took the max — so follow the larger of up and left. Following the smaller walks a path that was never optimal and prints a shorter string with total confidence.
Characters match during the walk. What do you do?
A match was banked by the fill, so it belongs in the answer and both strings shrink. Because you are walking backwards the characters come out reversed — remember to flip the string at the end, which is the one step everyone forgets.
“Print” or “return the subsequence” rather than its length. The table already holds the answer; the work is reading it back out.
Start at the bottom-right and retrace the decisions the fill made. On a match, that character was banked — record it and step diagonally. On a mismatch, the fill took the larger neighbour, so follow the larger. Because you walk backwards, the characters come out reversed.
string printLCS(string& a, string& b) { int n = a.size(), m = b.size(); vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); // full table needed for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j] = (a[i-1] == b[j-1]) ? 1 + dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]); string out; int i = n, j = m; while (i > 0 && j > 0) { if (a[i-1] == b[j-1]) { out += a[i-1]; i--; j--; } // on the diagonal else if (dp[i-1][j] > dp[i][j-1]) i--; // follow the LARGER else j--; } reverse(out.begin(), out.end()); // walked backwards, so flip it return out; }
def printLCS(a, b): n, m = len(a), len(b) dp = [[0]*(m+1) for _ in range(n+1)] # full table needed for i in range(1, n+1): for j in range(1, m+1): dp[i][j] = ((1 + dp[i-1][j-1]) if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])) out, i, j = [], n, m while i > 0 and j > 0: if a[i-1] == b[j-1]: out.append(a[i-1]); i -= 1; j -= 1 # on the diagonal elif dp[i-1][j] > dp[i][j-1]: i -= 1 # follow the LARGER else: j -= 1 return ''.join(reversed(out)) # walked backwards, so flip
Space-optimising the fill to two rows and then trying to walk back. The walk needs every cell, so this is the one problem in the deck where the O(m) optimisation is not available — a real trade, not an oversight.
One cell of difference, and a different place to read the answer
SAME TWO STRINGS, BUT THE COMMON PART MUST BE CONSECUTIVE. WHAT CHANGES?
The lecture stresses the difference between the two words. What is it?
Consecutiveness is the whole delta, and it is what forbids the max-of-neighbours branch: the moment characters disagree, any run in progress is broken and the count must restart at zero rather than inheriting.
Characters DON'T match. What goes in the cell?
'You are not dependent on the previous guys, because you don't want any interruption.' Inheriting the neighbour's value is exactly the LCS behaviour, and it is what would let a broken run continue. This one cell is the entire difference between the two problems.
Where does the answer live at the end?
Each cell is the length of a run ENDING exactly there, so the best run may end anywhere. Reading the corner gives you the run that happens to end at both string ends — usually 0. Same shape as deck I's variable-ending-point problems.
abcde against abfce, but now the run must be consecutive. Identical table, identical matching branch, and on a mismatch the cell becomes 0 instead of inheriting a neighbour. The answer is no longer the corner, either: it is the largest cell anywhere.
The word substring rather than subsequence, or the word “consecutive”. Everything else is identical to #01.
A run of matching characters cannot survive an interruption, so the moment two characters disagree the cell drops to 0 rather than inheriting a neighbour. Each cell then means 'the longest run ENDING exactly here' — and because a run may end anywhere, the answer is the largest cell in the table rather than the corner.
int longestCommonSubstring(string& a, string& b) { int n = a.size(), m = b.size(), best = 0; vector<int> prev(m + 1, 0), cur(m + 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i-1] == b[j-1]) { cur[j] = 1 + prev[j-1]; best = max(best, cur[j]); // answer is the LARGEST cell } else { cur[j] = 0; // the run BREAKS - inherit nothing } } prev = cur; } return best; }
def longestCommonSubstring(a, b): m, best = len(b), 0 prev = [0] * (m + 1) for i in range(1, len(a) + 1): cur = [0] * (m + 1) for j in range(1, m + 1): if a[i-1] == b[j-1]: cur[j] = 1 + prev[j-1] best = max(best, cur[j]) # answer is the LARGEST cell else: cur[j] = 0 # the run BREAKS prev = cur return best
Reading the bottom-right cell. It is the run that ends at BOTH string ends, which is usually 0 — so the function returns 0 for inputs with an obvious common run, and occasionally returns the right answer by coincidence.
Reversing a string to reuse a solved problem
WHAT IS THE LONGEST PALINDROME HIDING INSIDE THIS STRING AS A SUBSEQUENCE?
The longest palindromic subsequence of s equals what?
A palindrome reads the same forwards and backwards, so it appears in both s and reverse(s) — and any subsequence common to both is a palindrome. Nine minutes of lecture because there is no new recurrence, just a reversed string handed to a solved function.
Why must the reduction use LCS rather than longest common SUBSTRING?
'bbbab' has palindromic subsequence 'bbb', which is not contiguous. Using substring would return only the longest contiguous palindrome — a real but different problem. The previous unit's distinction, cashed in immediately.
s = "bbbab". What is the length of its longest palindromic subsequence?
"bbbb" — take the three b's plus the trailing b, skipping the a. Length 4. The greedy read of 'bbb' at the front gives 3 and misses that the last b joins them; the table does not miss it.
One string, and “longest palindromic subsequence”. A single-string problem that becomes a two-string problem the moment you write the string twice.
A palindrome reads identically forwards and backwards, so it appears in s AND in reverse(s) — and conversely, anything common to both reads the same either way. So the answer is LCS(s, reverse(s)) and there is no new recurrence to write.
int longestPalindromeSubseq(string s) { string t = s; reverse(t.begin(), t.end()); // a palindrome lives in s AND reverse(s) return lcs(s, t); // no new recurrence at all }
def longestPalindromeSubseq(s): return lcs(s, s[::-1]) # a palindrome lives in s AND reverse(s)
Reaching for longest common substring instead. On 'bbbab' that returns 3 rather than 4, because the answer 'bbbb' is not contiguous — a smaller, plausible number from the wrong one of two nearly identical tables.
Two reductions stacked — insertions counted without ever placing one
HOW FEW CHARACTERS CAN YOU INSERT TO TURN THIS STRING INTO A PALINDROME?
Minimum insertions to make s a palindrome equals what?
Whatever already forms a palindrome can be kept; every other character needs a partner inserted. So the cost is n − LPS, and LPS is the previous unit. Two reductions stacked — this is LCS underneath, twice removed.
The lecture stresses one freedom in the problem statement. Which?
'You can insert any character anywhere — that's the point.' If insertions were end-only the answer would be different and larger. The freedom is what lets every unmatched character be paired independently, which is what makes n − LPS exact.
s = "abcaa", whose longest palindromic subsequence is "aca" (length 3). Minimum insertions?
5 − 3 = 2. The three characters of "aca" stay put and the other two each need a mirror inserted. Note you never have to work out WHERE they go — the count alone answers the question.
“Minimum insertions to make it a palindrome”, with insertions allowed anywhere. Two reductions deep: this is LPS, which is LCS.
Whatever already forms a palindrome can be left alone; every other character needs a mirror inserted opposite it. So the cost is n minus the longest palindromic subsequence. Because insertions may go anywhere, each unmatched character can be paired independently — which is what makes the count exact.
int minInsertions(string s) { // whatever already forms a palindrome stays; everything else needs // a mirror inserted somewhere - and insertions may go ANYWHERE. return (int)s.size() - longestPalindromeSubseq(s); }
def minInsertions(s): # whatever already forms a palindrome stays; everything else needs # a mirror inserted somewhere - and insertions may go ANYWHERE. return len(s) - longestPalindromeSubseq(s)
Assuming insertions must go at the ends. They may go anywhere, and restricting them gives a larger answer that is correct for a different problem. Reading that one clause of the statement is the whole difficulty.
Two operations, both priced off the same table
HOW FEW INSERTIONS AND DELETIONS TURN STRING A INTO STRING B?
Converting A to B with insertions and deletions only. What is the total cost?
The LCS survives untouched. Everything else in A is deleted and everything else in B is inserted, so the cost is the two leftovers added. Third reduction to the same table in four units — which is the point the deck keeps making.
Why is the LCS specifically the right thing to keep?
Order matters because insertions and deletions cannot reorder anything. A common SET of characters would be useless — they must appear in the same relative order in both, which is precisely the definition of a common subsequence.
A = "abcd" (4), B = "anc" (3), LCS = "ac" (2). Total operations?
(4 − 2) deletions + (3 − 2) insertions = 2 + 1 = 3. Delete b and d, insert n. Counting them separately and adding is the whole method — there is nothing to simulate.
“Convert A to B” with insertions and deletions but no replacement. The absence of replace is what keeps this at LCS rather than at edit distance.
The longest common subsequence survives both operations untouched — it is already in the right order in both strings. Everything A has beyond it must be deleted, and everything B has beyond it must be inserted. So the cost is the two leftovers added, and no simulation is needed.
int minOperations(string& a, string& b) { int k = lcs(a, b); // the common part survives untouched return (a.size() - k) // delete what A has beyond it + (b.size() - k); // insert what B has beyond it }
def minOperations(a, b): k = lcs(a, b) # the common part survives untouched return (len(a) - k) + (len(b) - k)
Subtracting the LCS once instead of twice. That gives the length of the shortest common SUPERSEQUENCE — a real quantity, for the next problem. The same three numbers answer two different questions, and confusing them never crashes.
Building a string by merging two, sharing what they have in common
WHAT IS THE SHORTEST STRING THAT CONTAINS BOTH OF THESE AS SUBSEQUENCES?
The shortest string containing both A and B as subsequences has what length?
Write both out and merge them; every character of the LCS is shared and so written once rather than twice. Subtracting twice would delete the shared characters entirely rather than de-duplicating them.
The lecture names two prerequisites in its first minute. Which pair?
You need the table AND the backward walk, because the answer is a STRING and building it means retracing the fill. This is where unit 02's technique stops being optional and becomes the only way through.
Walking the table backwards to BUILD the supersequence, what happens when characters don't match?
A non-matching character belongs to exactly one string and still has to appear, so it is written as you step past it. Matching characters are written once on the diagonal. Same walk as unit 02, but emitting more.
“Shortest string containing both as subsequences.” A construction problem: the answer is a string, so the table alone is not enough.
Write both strings out and merge them, sharing every character of the LCS rather than writing it twice — so the length is n + m − LCS. Building the actual string means walking the table backwards, emitting the shared characters once on the diagonal and the unshared ones as you step past them.
string shortestCommonSupersequence(string a, string b) { int n = a.size(), m = b.size(); vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j] = (a[i-1] == b[j-1]) ? 1 + dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]); // length is n + m - lcs; build it by walking the table backwards string out; int i = n, j = m; while (i > 0 && j > 0) { if (a[i-1] == b[j-1]) { out += a[i-1]; i--; j--; } // written ONCE else if (dp[i-1][j] > dp[i][j-1]) { out += a[i-1]; i--; } else { out += b[j-1]; j--; } } while (i > 0) { out += a[i-1]; i--; } // whatever is left over while (j > 0) { out += b[j-1]; j--; } reverse(out.begin(), out.end()); return out; }
def shortestCommonSupersequence(a, b): n, m = len(a), len(b) dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, m+1): dp[i][j] = ((1 + dp[i-1][j-1]) if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])) out, i, j = [], n, m while i > 0 and j > 0: if a[i-1] == b[j-1]: out.append(a[i-1]); i -= 1; j -= 1 # written ONCE elif dp[i-1][j] > dp[i][j-1]: out.append(a[i-1]); i -= 1 else: out.append(b[j-1]); j -= 1 out += list(a[:i])[::-1] + list(b[:j])[::-1] # whatever is left over return ''.join(reversed(out))
Emitting the matched character twice — once for each string. The result still contains both as subsequences, so it passes casual inspection, and it is simply not the shortest. Sharing the LCS is the entire point of the problem.
The one string table where a match is not forced
HOW MANY DISTINCT WAYS CAN THE SECOND STRING BE CARVED OUT OF THE FIRST?
The lecture names the giveaway that this is a counting problem. What is it?
'Whenever the problem is count ways, the base case has to return one or has to return zero, and then you add up the branches.' Same rule deck I used on climbing stairs — the pattern is stated as a general recipe rather than as a fact about this problem.
Characters at i and j match. What does the count do?
Unlike LCS, a match here is not forced — that s-character could be used for this t-character or saved for a later one, and both give valid distinct subsequences. So both branches count and they add. This is the one place matching does NOT mean 'take it'.
Characters DON'T match. What happens?
You are carving t out of s, so s may be skipped freely but t must be matched in order. An unmatched s character is simply discarded. The asymmetry — one string free, one string fixed — is what distinguishes this from every other table in the deck.
Base cases: what is the count when t is exhausted, and when s is exhausted but t is not?
An empty t has been fully matched — that is one complete way. A non-empty t with no s left can never be completed — zero ways. Getting these backwards inverts the entire answer, and they are the reason the counting rule above is stated the way it is.
How many ways can rabbit be carved out of rabbbit? Three, and the reason is the matching branch: that b could be used here or saved for later, so both branches count and they ADD. Every other string table in this deck treats a match as forced; this one does not.
“How many distinct subsequences of s equal t.” Counting rather than measuring, over two strings — and note the asymmetry: t must be matched in order, s may be skipped freely.
This is the one string table where a match is NOT forced. That s-character can serve this t-character, or be saved for a later one, and both give valid distinct subsequences — so the branches add. On a mismatch only the skip-s branch survives, because t may never be skipped.
int numDistinct(string s, string t) { int n = s.size(), m = t.size(); vector<double> prev(m + 1, 0), cur(m + 1, 0); prev[0] = cur[0] = 1; // empty target: exactly one way for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i-1] == t[j-1]) cur[j] = prev[j-1] + prev[j]; // USE it, or SAVE it - ADD else cur[j] = prev[j]; // skip s; t cannot move } prev = cur; } return (int)prev[m]; }
def numDistinct(s, t): m = len(t) prev = [0] * (m + 1) prev[0] = 1 # empty target: exactly one way for i in range(1, len(s) + 1): cur = [0] * (m + 1) cur[0] = 1 for j in range(1, m + 1): if s[i-1] == t[j-1]: cur[j] = prev[j-1] + prev[j] # USE it, or SAVE it - ADD else: cur[j] = prev[j] # skip s; t cannot move prev = cur return prev[m]
Treating a match as forced, out of habit from LCS. Taking only the diagonal undercounts every case where a character could have been used later — the answer comes out smaller and completely believable.
Three branches per cell — the first table in the step that needs them
HOW FEW EDITS TURN ONE STRING INTO ANOTHER, WITH INSERT, DELETE AND REPLACE?
Characters don't match. How many options does the recurrence try?
Insert (j−1), delete (i−1) and replace (both back), each costing 1, and you take the min of the three. Deck I and II had two branches per cell; this is the first table in the whole step with three.
Characters DO match. What is the cost?
Nothing needs doing, so no cost is added and both indices advance. Charging 1 here is the classic slip and it inflates the answer by exactly the length of the LCS — a wrong number that scales plausibly with the input.
One string is empty. What is the edit distance?
Every remaining character has to be inserted or deleted, one operation each. This is why the tabulated version fills row 0 with 0..m and column 0 with 0..n rather than with zeros — the base cases are a ramp, not a flat edge.
The lecture's own example: "exection" to "execution". What is the distance?
One insertion — 'u' after 'exec'. The strings differ in length by exactly one and share everything else in order, so a single operation suffices. Worth doing by eye before trusting a table: a sanity check you can run in an interview.
horse to ros. The first table in this whole step that reads three cells: insert from the left, delete from above, replace from the diagonal, each costing one. A match costs nothing and slides across the diagonal, and the base row is a ramp, not a row of zeros.
“Minimum operations to convert” with insert, delete AND replace. The third operation is what makes this three branches rather than two.
At each pair of positions: if the characters match, nothing needs doing and you slide diagonally at no cost. If they do not, you may insert (advance the target), delete (advance the source) or replace (advance both), each costing one — take the cheapest. The base cases are ramps, because converting to or from an empty string costs one operation per remaining character.
int minDistance(string a, string b) { int n = a.size(), m = b.size(); vector<int> prev(m + 1), cur(m + 1); for (int j = 0; j <= m; j++) prev[j] = j; // base row is a RAMP for (int i = 1; i <= n; i++) { cur[0] = i; // base column too for (int j = 1; j <= m; j++) { if (a[i-1] == b[j-1]) cur[j] = prev[j-1]; // a match is FREE else cur[j] = 1 + min({cur[j-1], // insert prev[j], // delete prev[j-1]}); // replace } prev = cur; } return prev[m]; }
def minDistance(a, b): m = len(b) prev = list(range(m + 1)) # base row is a RAMP for i in range(1, len(a) + 1): cur = [i] + [0] * m # base column too for j in range(1, m + 1): if a[i-1] == b[j-1]: cur[j] = prev[j-1] # a match is FREE else: cur[j] = 1 + min(cur[j-1], # insert prev[j], # delete prev[j-1]) # replace prev = cur return prev[m]
Charging 1 for a matching pair. It inflates the answer by exactly the length of the common subsequence — a number that grows sensibly with the input, never crashes, and is wrong on every input with any characters in common.
A pattern with power on one side, literal text on the other
DOES THIS PATTERN, WITH ? AND *, MATCH THIS STRING?
What does '?' match, and what does '*' match?
'?' is a single-character slot; '*' can absorb nothing at all or the entire rest of the string. That 'including empty' is what makes '*' two branches rather than one, and forgetting it fails on the shortest inputs.
The pattern is p and the string is s. Where can the wildcards appear?
'This question mark or the star will only be in string s1, it will not be in s2.' The asymmetry is what makes this a matching problem rather than a comparison — one side is a pattern with power, the other is literal text.
The pattern character is '*'. What are the two branches?
OR the two: consume nothing and move past the '*', or let it swallow one more character of s and stay on the '*'. Repeated, that covers every possible length — and the 'stay on the star' branch is the same stay-put move unbounded knapsack used.
The string is exhausted but pattern characters remain. When is it still a match?
'*' can match the empty sequence, so trailing stars are harmless; anything else demands a character that no longer exists. Returning false unconditionally here is the most common wildcard bug and it fails only on inputs ending in stars.
A pattern containing ? and * against a literal string. The asymmetry is the tell: one side has power, the other is text.
? consumes exactly one character, so it behaves like a match. * is the interesting one: it may consume nothing at all, or swallow one more character and remain available — two branches, OR-ed. Repeated, that covers every possible length, and the 'stay put' branch is the same move unbounded knapsack used in deck II.
bool isMatch(string s, string p) { int n = s.size(), m = p.size(); vector<bool> prev(m + 1, false), cur(m + 1, false); prev[0] = true; // empty pattern, empty string for (int j = 1; j <= m; j++) // leading stars match empty prev[j] = prev[j-1] && p[j-1] == '*'; for (int i = 1; i <= n; i++) { cur[0] = false; // non-empty s, empty pattern for (int j = 1; j <= m; j++) { if (p[j-1] == '*') cur[j] = prev[j] // swallow one more, stay on * || cur[j-1]; // match nothing, move past * else if (p[j-1] == '?' || p[j-1] == s[i-1]) cur[j] = prev[j-1]; else cur[j] = false; } prev = cur; } return prev[m]; }
def isMatch(s, p): m = len(p) prev = [False] * (m + 1) prev[0] = True # empty pattern, empty string for j in range(1, m + 1): # leading stars match empty prev[j] = prev[j-1] and p[j-1] == '*' for i in range(1, len(s) + 1): cur = [False] * (m + 1) for j in range(1, m + 1): if p[j-1] == '*': cur[j] = prev[j] or cur[j-1] # swallow one more, or move past elif p[j-1] == '?' or p[j-1] == s[i-1]: cur[j] = prev[j-1] prev = cur return prev[m]
Returning false whenever the string is exhausted and pattern remains. Trailing stars match the empty sequence, so this fails exactly on inputs ending in '*' — a narrow, easily-missed slice of the test cases.
A stock answer with no state at all — the baseline the rest add to
ONE BUY AND ONE SELL. WHAT IS THE MOST YOU CAN MAKE?
One buy, one sell, sell must come after buy. What does the one-pass solution track?
At each day, the best sale today is today's price minus the cheapest day before it — so one variable for the running minimum and one for the best profit. No table, no state: this row is here to show what the LATER rows are adding state to.
The lecture insists on watching this section in order. Why does it say that matters?
'In DP on stocks people tend to expect you to answer the space optimisation technique.' Each row adds exactly one thing to the state, so arriving at #14 cold means meeting three additions at once instead of one.
What is the answer when prices only ever fall?
Doing nothing is legal, so profit is floored at 0 and never negative. Every later row inherits this floor, which is why their 'not holding, no transactions used' state starts at 0 rather than at minus infinity.
One buy, one sell, and the sell must come after the buy. No DP is needed — this row is here to establish the baseline the next five add to.
The best sale on day i is today's price minus the cheapest day before it. So sweep once carrying the running minimum and the best profit against it. Profit is floored at 0 because doing nothing is legal — a floor every later problem inherits.
int maxProfit(vector<int>& p) { int best = 0, cheapest = p[0]; // no table, no state for (int i = 1; i < (int)p.size(); i++) { best = max(best, p[i] - cheapest); // sell today at the best buy so far cheapest = min(cheapest, p[i]); } return best; // floored at 0: doing nothing is legal }
def maxProfit(p): best, cheapest = 0, p[0] # no table, no state for x in p[1:]: best = max(best, x - cheapest) # sell today at the best buy so far cheapest = min(cheapest, x) return best # floored at 0: doing nothing is legal
Returning a negative number when prices only fall. Doing nothing is always an option, so the answer is 0 — and every later problem's 'not holding' state starts at 0 for the same reason.
The flag, and the two moves it permits
UNLIMITED TRANSACTIONS, ONE SHARE AT A TIME. WHAT DOES THE STATE HAVE TO REMEMBER?
Unlimited transactions, but you may hold at most one share. What does the state become?
Two states per day, and the flag decides which two moves are legal: holding lets you sell or wait; not holding lets you buy or wait. Carrying the BUY PRICE instead would make the state unbounded — the flag is what keeps it O(n).
You are holding a share on day i. Which two moves are available?
Exactly two, and this is pick / not-pick wearing a different word. Both branches are evaluated and the max kept, which is why the whole family is a DP rather than a scan — even though this particular row also has a one-line greedy answer.
There is a greedy one-liner for this row: sum every positive day-to-day difference. Why does it work here?
With no transaction limit, buying at every local minimum and selling at every local maximum is achievable, and that sum equals the total of positive deltas. Add a cap on transactions — the very next row — and the argument collapses, which is exactly why #13 needs the table.
Prices [7, 1, 5, 3, 6, 4]. Two rows, not holding and holding, and the day walking across. A negative cell is money spent, not a bug. Watch the flag flip: every later row in this section adds exactly one thing to this table and nothing else.
“As many transactions as you like”, but at most one share held. The phrase 'at most one share' is what introduces the state.
Two states per day: holding, or not. Holding lets you sell or keep; not holding lets you buy or wait. Carrying the BUY PRICE instead of a flag would make the state as large as the array — the profit already accounts for what you paid, so the price does not need remembering.
int maxProfit(vector<int>& p) { int free = 0, hold = -p[0]; for (int i = 1; i < (int)p.size(); i++) { int pf = free, ph = hold; free = max(pf, ph + p[i]); // wait, or SELL hold = max(ph, pf - p[i]); // keep, or BUY } return free; // never end holding a share }
def maxProfit(p): free, hold = 0, -p[0] for x in p[1:]: free, hold = max(free, hold + x), max(hold, free - x) return free # never end holding a share
Putting the purchase price into the state. It turns 2n cells into n², which is fatal at n = 10⁵ — and it is unnecessary, because a negative running profit already encodes exactly what was spent.
A cap, and why greedy stops working the moment one exists
AT MOST TWO TRANSACTIONS. WHICH RISES ARE WORTH SPENDING ONE ON?
At most two transactions. What does the state gain over the previous row?
Day, holding flag, and a cap counter — three indices. The greedy from #12 dies here because capturing every rise may use more than two transactions, so you must choose which rises are worth spending a transaction on.
When is the transaction counter decremented?
A buy-and-sell pair is one transaction, so decrementing on either would be consistent — but decrementing on the sell means an unsold share never consumes the budget, which matches how the constraint reads. Decrementing on BOTH is the real bug and it halves your allowance.
The state is (day, holding, capLeft). How large is the table?
Two boolean states and three cap values gives 6n cells — still linear, which is why the sheet is comfortable calling this Medium. Recognising that a small extra dimension does not change the complexity class is the point of the row.
“At most two transactions.” A cap on how many trades — and the moment a cap exists, the greedy from the previous row stops being correct.
Add a third index counting transactions remaining. The greedy 'capture every rise' fails because capturing every rise may take more than two trades, so you must choose which rises are worth spending one on — and choosing is what a table does. The counter decrements on the sell, when a transaction actually completes.
int maxProfit(vector<int>& p) { int n = p.size(), K = 2; // dp[hold][capLeft] - the cap dimension is the whole addition vector<vector<int>> dp(2, vector<int>(K + 1, 0)); for (int c = 0; c <= K; c++) dp[1][c] = -1e9; for (int i = 0; i < n; i++) { auto nxt = dp; for (int c = 1; c <= K; c++) { nxt[1][c] = max(dp[1][c], dp[0][c] - p[i]); // buy nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + p[i]); // SELL: cap-- } dp = nxt; } return max({dp[0][0], dp[0][1], dp[0][2]}); }
def maxProfit(p): K = 2 NEG = float('-inf') # dp[hold][capLeft] - the cap dimension is the whole addition dp = [[0]*(K+1), [NEG]*(K+1)] for x in p: nxt = [row[:] for row in dp] for c in range(1, K + 1): nxt[1][c] = max(dp[1][c], dp[0][c] - x) # buy nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + x) # SELL: cap-- dp = nxt return max(dp[0])
Decrementing the cap on the buy AND the sell. A buy-and-sell pair is one transaction, so charging twice halves your allowance — and the answer is merely lower, never obviously broken.
A constant becoming a parameter, for free
NOW THE CAP IS k INSTEAD OF 2. HOW MUCH OF THE CODE CHANGES?
Transactions capped at k rather than 2. What changes in the code?
A twelve-minute lecture, because a constant became a parameter. Exactly the Frog Jump to Frog Jump-with-K move from deck I — and recognising that a generalisation is free is worth as much as being able to do it.
What is the complexity now?
n days × 2 holding states × k caps. Worth noticing that when k ≥ n/2 the cap can never bind, so the problem degenerates to the unlimited case — a real optimisation and a real interview follow-up.
Why does this deck ship it as a DIFF against problem #13 rather than in full?
A delta shows what a generalisation costs — almost nothing — where two full listings would hide it in duplicated code. The deck reserves diffs for exactly this: a change small enough that seeing only the change is more informative than seeing the whole.
The previous problem with the 2 replaced by a parameter k. A constant becoming a parameter always means the loop was already there.
Nothing about the recurrence changes — the cap dimension simply runs to k rather than to 2. Worth knowing the degenerate case: once k ≥ n/2 the cap can never bind, because there are not enough days to make that many trades, and the problem collapses to the unlimited version.
-int maxProfit(vector<int>& p) {- int n = p.size(), K = 2;- // dp[hold][capLeft] - the cap dimension is the whole addition+int maxProfit(int K, vector<int>& p) {+ int n = p.size();+ if (n == 0 || K == 0) return 0; vector<vector<int>> dp(2, vector<int>(K + 1, 0)); for (int c = 0; c <= K; c++) dp[1][c] = -1e9; for (int i = 0; i < n; i++) { auto nxt = dp; for (int c = 1; c <= K; c++) {- nxt[1][c] = max(dp[1][c], dp[0][c] - p[i]); // buy- nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + p[i]); // SELL: cap--+ nxt[1][c] = max(dp[1][c], dp[0][c] - p[i]);+ nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + p[i]); } dp = nxt; }- return max({dp[0][0], dp[0][1], dp[0][2]});+ return *max_element(dp[0].begin(), dp[0].end()); }
-def maxProfit(p):- K = 2+def maxProfit(K, p):+ if not p or K == 0:+ return 0 NEG = float('-inf')- # dp[hold][capLeft] - the cap dimension is the whole addition dp = [[0]*(K+1), [NEG]*(K+1)] for x in p: nxt = [row[:] for row in dp] for c in range(1, K + 1):- nxt[1][c] = max(dp[1][c], dp[0][c] - x) # buy- nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + x) # SELL: cap--+ nxt[1][c] = max(dp[1][c], dp[0][c] - x)+ nxt[0][c-1] = max(nxt[0][c-1], dp[1][c] + x) dp = nxt return max(dp[0])
Allocating the table before checking k. A judge may hand you k = 10⁹ with n = 10³, and a k-sized dimension blows memory instantly — where the k ≥ n/2 shortcut answers it in linear time.
A constraint expressed as a longer reach
AFTER SELLING YOU MUST SIT OUT A DAY. WHERE DOES THAT GO IN THE RECURRENCE?
After selling you must skip a day. How is that expressed in the recurrence?
Selling on day i−1 means you cannot buy on day i, so buying looks back two days instead of one. A separate cooldown state also works and is what many write-ups do; the two-day reach is the shorter expression of the same rule.
Which index must be guarded once the buy branch reaches back two days?
Precisely the guard deck I put on Frog Jump's two-step branch — the same off-by-one, three decks apart, because the same thing causes it: a recurrence that reaches further back than the array has room for.
Does the cooldown apply after BUYING as well as after selling?
The constraint is stated for sales alone. Applying it to buys as well is a misreading that produces a lower, entirely believable profit — the kind of wrong answer that comes from skimming the statement rather than from bad code.
“After you sell, you cannot buy the next day.” A constraint that reaches across days rather than adding a new decision.
Selling on day i−1 forbids buying on day i. So the buy branch looks back two days instead of one, and everything else is problem #12 unchanged. A separate 'cooldown' state also works; the two-day reach is the shorter way of saying the same thing — and it needs the same i−2 guard Frog Jump needed in deck I.
int maxProfit(vector<int>& p) { int n = p.size(); vector<int> free(n + 2, 0), hold(n + 2, -1e9); hold[n] = hold[n+1] = -1e9; for (int i = n - 1; i >= 0; i--) { free[i] = max(free[i+1], hold[i+1] + p[i]); // wait, or SELL // after BUYING, you could only have been free since i+2 - the COOLDOWN hold[i] = max(hold[i+1], free[i+2] - p[i]); } return free[0]; }
def maxProfit(p): n = len(p) NEG = float('-inf') # free[i] = best from day i onward, not holding; hold[i] = holding free = [0] * (n + 2) hold = [NEG] * (n + 2) for i in range(n - 1, -1, -1): free[i] = max(free[i+1], hold[i+1] + p[i]) # wait, or SELL # after buying you may only have been free since i+2 - the COOLDOWN hold[i] = max(hold[i+1], (free[i+2] if i + 2 <= n else 0) - p[i]) return free[0]
Applying the cooldown after buying as well. The statement restricts sales only, and the stricter reading gives a lower, entirely plausible profit — a misreading rather than a bug, which is why it survives code review.
A change to a value, not to a state
EVERY COMPLETED TRADE COSTS A FEE. DOES THE STATE HAVE TO GROW?
A fee is charged per completed transaction. Where does it go in the recurrence?
One fee per completed transaction, and a transaction completes at the sell — so subtract it there and the state does not grow at all. Charging on both halves double-counts and quietly halves your profit on fee-heavy inputs.
How does the state compare with problem #12, unlimited transactions?
The fee changes a VALUE, not a state — which is why this is the gentlest row in the section despite arriving last. Distinguishing 'this changes what a cell is worth' from 'this changes what a cell means' is the whole skill of state design.
Why does the greedy 'sum every positive difference' fail once a fee exists?
Several small rises that were each profitable individually can be worth less than one longer hold once the fee is charged per trade. The table weighs holding against trading automatically; greedy has to be told, and cannot be told locally.
“A fee for each transaction.” Note what this does NOT add: no cap, no cooldown, no extra index. The state is untouched.
Subtract the fee once, at the point a transaction completes — the sell. The state does not grow at all, because the fee changes what a cell is WORTH rather than what it MEANS. That distinction is the whole of state design, and this is the cleanest example of it in the deck.
int maxProfit(vector<int>& p, int fee) { int free = 0, hold = -p[0]; for (int i = 1; i < (int)p.size(); i++) { int pf = free, ph = hold; free = max(pf, ph + p[i] - fee); // the fee is charged ONCE, here hold = max(ph, pf - p[i]); } return free; }
def maxProfit(p, fee): free, hold = 0, -p[0] for x in p[1:]: free, hold = max(free, hold + x - fee), max(hold, free - x) return free # the fee is charged ONCE, on the sell
Charging the fee on both the buy and the sell. One trade is one fee; charging twice quietly halves the profit on fee-heavy inputs and leaves it correct when the fee is 0 — which is exactly the test case people check.
A mismatch in longest common SUBSTRING sets the cell to…
Zero, always. Consecutiveness means an interrupted run cannot continue, so nothing is inherited. Inheriting a neighbour is precisely the LCS behaviour, and it is the single cell of difference between the two problems.
Longest palindromic subsequence of s is computed how?
A palindrome is common to s and reverse(s), and any subsequence common to both reads the same either way. Minimum insertions to make s a palindrome then falls out as n minus this — two problems solved by one reversal and no new recurrence.
Converting A to B with insertions and deletions only costs…
Two leftovers. Delete what A has beyond the LCS, insert what B has beyond it. Subtracting the LCS only once gives the SHORTEST COMMON SUPERSEQUENCE's length instead — the same three quantities rearranged, which is why the two get confused.
Distinct Subsequences: characters match. What does the transition do?
This is the one table where a match is not forced. That source character can serve this target character or be saved for a later one, and both produce valid distinct subsequences — so both count and they add. Every other string problem here banks a match unconditionally.
Wildcard matching: the pattern character is *. What are the branches?
OR the two. Staying on the star while consuming one more character is the same stay-put move unbounded knapsack used in deck II — and it is the branch that lets one star cover any length. Forgetting the empty case fails on the shortest inputs.
Stock problems: what does adding a cap of k transactions do to the complexity?
One more dimension, one more factor. Still polynomial and still cheap. Worth knowing the corollary too: once k ≥ n/2 the cap can never bind, so the problem collapses to the unlimited case — a genuine optimisation and a standard follow-up question.
Every one of these returns a number. Three of them return a number that is merely too small, which is the hardest kind to notice — the code runs, the samples pass, and the judge disagrees on a case you never thought to try.
if (a[i-1]==b[j-1]) return 1 + f(i-1,j-1);. A match is free. The 1 inflates every answer by exactly the LCS length — plausible, monotonic in the input, and wrong.
A mismatch must reset the cell to 0. Take max(up, left) instead and you have silently written LCS, which returns a longer answer for a question about consecutive runs.
Each cell is a run ENDING there, so the best run may end anywhere. The bottom-right cell is the run ending at both string ends — usually 0, occasionally right by accident.
Insert-and-delete cost is n + m − 2·LCS; the shortest common supersequence is n + m − LCS. The same three numbers answer two different questions and swapping them never crashes.
Taking only the diagonal on a match undercounts, because that source character could have been saved for a later target character. The answer is smaller and entirely believable.
It turns 2n states into n², and for n = 10⁵ that is fatal. The profit already accounts for what was paid; a boolean holding flag is all the state the problem needs.
Fifteen rows, two tables. Everything above the line is the LCS grid read differently; everything below it is one array and a flag.
Ten string problems and one table: characters match, so bank them and step diagonally; they do not, so try both drops and keep the better. Change the mismatch to a zero and it counts consecutive runs; feed it a reversed string and it finds palindromes; subtract its answer from the lengths and it prices insertions and deletions. Then six stock problems that abandon the second string entirely and carry a flag instead — holding or not, transactions left, one day of cooldown, a fee. Deck IV is the last one: subsequences that must increase, and the partition DP where you choose where to CUT rather than what to take.
Deck 3 of 4. Lectures DP 25-40 of 56, sixteen against sixteen sheet rows — the only exactly one-to-one slice in the playlist. Every drill cites its lecture transcript; every bench fills in numbers the build re-derived; and every code listing in this deck was executed against the judge's own examples before it shipped.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.