Why this matters when you build with AI
When an AI tool returns text, you often need to compare it with a reference. A test may ask how far a model's extracted invoice number is from the expected one, or how much a prompt changed between two versions. Those are edit distance questions: the smallest number of insertions, deletions and replacements that turn one string into another. Longest common subsequence (LCS) is the core of many diff and merge tools.
These problems are also where AI-written code goes wrong most often. A model can produce a table that compiles and prints a number that looks plausible. The usual faults are a missing base case (the row and column for the empty prefix), swapping the cost of a deletion and an insertion, and a backtrack that walks the table in the wrong direction. You catch these faults with a second, slower program that tries every choice on tiny inputs. The C++ code in this lesson was checked that way.
Use this prompt when you ask a model for the code, so you can check the answer against the brute force program in this lesson:
Write C++17 code for weighted edit distance between two lowercase strings a and b.
Costs: deleting or inserting a letter c costs 1 if c is a, e, i, o or u, otherwise 2.
Replacing x by y costs 0 if x equals y, otherwise min(3, |x - y|), comparing alphabet positions.
Print the minimum cost and one optimal alignment, one operation per line.
Also write a brute force checker that tries every first operation with no memory,
and a main that compares the two on 2000 random pairs of length 0 to 5.
Good answer: a table with dp[0][j] and dp[i][0] set, the three-way minimum, a backtrack,
and a checker that prints mismatches=0. Check: the empty string against "ab" must cost 3.The idea: a table of prefixes
Dynamic programming (DP) solves a large problem by filling a table of answers to smaller problems and reusing them. For strings, the smaller problems are prefixes. A prefix is the first few characters of a string, so "lea" is the prefix of length 3 of "lean".
Let a and b be the two strings. Define dp[i][j] as the best cost for turning the first i characters of a into the first j characters of b. The answer for the whole strings is dp[n][m], where n and m are the two lengths.
Take a = "lean" and b = "lane" with the costs from the task in the next section. Deleting e costs 1 because e is a vowel. Deleting l costs 2 because it is not a vowel. Replacing e by a costs min(3, |4 - 0|), which is 3. A separate program that fills the same recurrence printed the full table for this pair:
'' l a n e
'' 0 2 3 5 6
l 2 0 1 3 4
e 3 1 2 4 3
a 4 2 1 3 4
n 6 4 3 1 2Read the bottom-right cell first. It is 2, which is the answer. The cell at row l and column l is 0 because the two characters match and nothing is paid. The first row and first column are the base cases: dp[0][j] is the cost of inserting the first j characters of b, and dp[i][0] is the cost of deleting the first i characters of a.
Every other cell depends on three neighbours. The diagonal neighbour means the two last characters are paired, either as a match or as a replacement. The upper neighbour means the last character of a is deleted. The left neighbour means the last character of b is inserted. The recurrence is this three-way minimum:
dp[i][j] = min(dp[i-1][j-1] + replace, dp[i-1][j] + delete, dp[i][j-1] + insert)
Because each cell only needs its three neighbours, you can fill the table in row order and never look ahead.
Standard technique: LCS, supersequences and rebuilding
A subsequence keeps the order of the characters but may skip some of them. A substring is a block of consecutive characters. The longest common subsequence (LCS) of two strings is the longest string that is a subsequence of both. In "abcde" and "ace" the LCS is "ace", length 3.
The LCS table uses the same shape. If the last characters match, dp[i][j] = dp[i-1][j-1] + 1. If they do not match, dp[i][j] is the larger of the upper and left cells. LCS is the same as edit distance with a special cost: deleting and inserting cost 1, and replacing is not allowed. That is why the shortest common supersequence is short to compute. A supersequence of two strings contains both as subsequences. Every character of the LCS is shared, so the shortest common supersequence has length n + m - LCS. For "abc" and "bd" the LCS is "b", so the length is 3 + 2 - 1 = 4. The program prints abdc, which contains both abc and bd.
Rebuilding the answer means walking the table back from the bottom-right cell and recording the choice at each step. For edit distance, the walk must find which of the three neighbours produced the value. For LCS, the walk takes a matched character whenever the last characters are equal and moves up or left otherwise. The code below keeps the whole table so the walk is possible.
Memory is the cost. The full table needs n * m integers. If you only need the number, keep two rows: the previous row and the row being filled. The memory drops to O(m). The rolling-row function in the code gives the same number, but it cannot print the alignment because the earlier rows are gone. To recover the alignment in linear memory, you use a divide and conquer method (usually called Hirschberg's method). I did not implement or test that method here.
The last variant is an LCS that must avoid a forbidden word t. A common subsequence that contains t as a substring is not allowed. The check cannot wait until the end, because by then the choice has been made. The fix is a state machine. The KMP automaton from lesson 01 (prefix function and KMP) tracks how much of t the chosen characters currently end with. The state is the length of the longest prefix of t that is a suffix of what has been chosen. A transition that would reach the full length of t is refused. The table gets a third index for the state, so its size is n * m * |t|.
For a = "lean", b = "lane" and forbidden "ea", the best answer is 3. The common subsequence "lan" does not contain "ea". A common subsequence of length 4 does not exist, because the LCS of the two strings is 3.
A Python version is fine for checking small cases and for reading the recurrence. I did not time Python against the sizes in the problem, so the C++ code is the reference. The C++ program below holds every function from this section, a brute force checker, and a demo. It compiles with g++ -O2 -std=c++17 -Wall -Wextra, with no warnings.
#include <bits/stdc++.h>
using namespace std;
// Costs for this task: deleting or inserting c costs 1 for a vowel, 2 otherwise.
// Replacing x by y costs 0 if x == y, else min(3, |x - y|).
bool is_vowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }
int indel_cost(char c) { return is_vowel(c) ? 1 : 2; }
int replace_cost(char x, char y) { return x == y ? 0 : min(3, abs(x - y)); }
// Full table DP with backtracking. Returns the cost and the alignment as lines:
// "M c" match, "S x y" substitute x by y, "D c" delete c from a, "I c" insert c from b.
pair<int, vector<string>> weighted_edit(const string& a, const 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++) dp[i][0] = dp[i - 1][0] + indel_cost(a[i - 1]);
for (int j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + indel_cost(b[j - 1]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int best = dp[i - 1][j - 1] + replace_cost(a[i - 1], b[j - 1]);
best = min(best, dp[i - 1][j] + indel_cost(a[i - 1]));
best = min(best, dp[i][j - 1] + indel_cost(b[j - 1]));
dp[i][j] = best;
}
vector<string> ops;
int i = n, j = m;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + replace_cost(a[i - 1], b[j - 1])) {
if (a[i - 1] == b[j - 1]) ops.push_back(string("M ") + a[i - 1]);
else ops.push_back(string("S ") + a[i - 1] + " " + b[j - 1]);
i--; j--;
} else if (i > 0 && dp[i][j] == dp[i - 1][j] + indel_cost(a[i - 1])) {
ops.push_back(string("D ") + a[i - 1]);
i--;
} else {
ops.push_back(string("I ") + b[j - 1]);
j--;
}
}
reverse(ops.begin(), ops.end());
return {dp[n][m], ops};
}
// Same cost using two rows only, so the memory is O(m).
int weighted_edit_rows(const string& a, const string& b) {
int n = a.size(), m = b.size();
vector<int> prev(m + 1), cur(m + 1);
for (int j = 1; j <= m; j++) prev[j] = prev[j - 1] + indel_cost(b[j - 1]);
for (int i = 1; i <= n; i++) {
cur[0] = prev[0] + indel_cost(a[i - 1]);
for (int j = 1; j <= m; j++) {
cur[j] = prev[j - 1] + replace_cost(a[i - 1], b[j - 1]);
cur[j] = min(cur[j], prev[j] + indel_cost(a[i - 1]));
cur[j] = min(cur[j], cur[j - 1] + indel_cost(b[j - 1]));
}
swap(prev, cur);
}
return prev[m];
}
// Checker: tries every first operation with no memory. Use only for strings of length 5 or less.
int brute_edit(const string& a, size_t i, const string& b, size_t j) {
if (i == a.size() && j == b.size()) return 0;
int best = INT_MAX;
if (i < a.size() && j < b.size())
best = min(best, replace_cost(a[i], b[j]) + brute_edit(a, i + 1, b, j + 1));
if (i < a.size()) best = min(best, indel_cost(a[i]) + brute_edit(a, i + 1, b, j));
if (j < b.size()) best = min(best, indel_cost(b[j]) + brute_edit(a, i, b, j + 1));
return best;
}
// LCS table: dp[i][j] = LCS length of a[0..i) and b[0..j).
vector<vector<int>> lcs_table(const string& a, const 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++) {
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
return dp;
}
string lcs_string(const string& a, const string& b) {
auto dp = lcs_table(a, b);
int i = a.size(), j = b.size();
string out;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) { out.push_back(a[i - 1]); i--; j--; }
else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
else j--;
}
reverse(out.begin(), out.end());
return out;
}
// Shortest common supersequence: its length is n + m - LCS.
string shortest_common_supersequence(const string& a, const string& b) {
auto dp = lcs_table(a, b);
int i = a.size(), j = b.size();
string out;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && a[i - 1] == b[j - 1]) { out.push_back(a[i - 1]); i--; j--; }
else if (j == 0 || (i > 0 && dp[i - 1][j] >= dp[i][j - 1])) { out.push_back(a[i - 1]); i--; }
else { out.push_back(b[j - 1]); j--; }
}
reverse(out.begin(), out.end());
return out;
}
// KMP automaton for the forbidden word t over 'a'..'z'. State |t| means "t has appeared".
vector<array<int, 26>> kmp_automaton(const string& t) {
int m = t.size();
vector<int> pi(m, 0);
for (int i = 1; i < m; i++) {
int k = pi[i - 1];
while (k > 0 && t[i] != t[k]) k = pi[k - 1];
if (t[i] == t[k]) k++;
pi[i] = k;
}
vector<array<int, 26>> go(m);
for (int st = 0; st < m; st++)
for (int c = 0; c < 26; c++) {
if (t[st] - 'a' == c) go[st][c] = st + 1;
else go[st][c] = st == 0 ? 0 : go[pi[st - 1]][c];
}
return go;
}
// Longest common subsequence of a and b that does not contain t as a substring.
// dp[i][j][k]: best length using a[0..i) and b[0..j), with the automaton in state k.
int lcs_avoiding(const string& a, const string& b, const string& t) {
int n = a.size(), m = b.size(), L = t.size();
auto go = kmp_automaton(t);
const int NEG = -1000000000;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(L, NEG)));
dp[0][0][0] = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k < L; k++) {
int v = dp[i][j][k];
if (v == NEG) continue;
if (i < n) dp[i + 1][j][k] = max(dp[i + 1][j][k], v);
if (j < m) dp[i][j + 1][k] = max(dp[i][j + 1][k], v);
if (i < n && j < m && a[i] == b[j]) {
int k2 = go[k][a[i] - 'a'];
if (k2 < L) dp[i + 1][j + 1][k2] = max(dp[i + 1][j + 1][k2], v + 1);
}
}
int best = 0;
for (int k = 0; k < L; k++) best = max(best, dp[n][m][k]);
return best;
}
// Replays an alignment and returns its cost, or -1 if it does not use a and b exactly.
int replay(const string& a, const string& b, const vector<string>& ops) {
size_t i = 0, j = 0;
int cost = 0;
for (const string& op : ops) {
if (op[0] == 'M') {
if (i >= a.size() || j >= b.size() || a[i] != b[j] || a[i] != op[2]) return -1;
i++; j++;
} else if (op[0] == 'S') {
if (i >= a.size() || j >= b.size() || a[i] != op[2] || b[j] != op[4]) return -1;
cost += replace_cost(op[2], op[4]); i++; j++;
} else if (op[0] == 'D') {
if (i >= a.size() || a[i] != op[2]) return -1;
cost += indel_cost(op[2]); i++;
} else {
if (j >= b.size() || b[j] != op[2]) return -1;
cost += indel_cost(op[2]); j++;
}
}
return (i == a.size() && j == b.size()) ? cost : -1;
}
int main() {
string a = "lean", b = "lane";
auto [cost, ops] = weighted_edit(a, b);
cout << "a=" << a << " b=" << b << " cost=" << cost << "\n";
for (const string& op : ops) cout << " " << op << "\n";
cout << "rows version: " << weighted_edit_rows(a, b) << "\n";
cout << "brute force: " << brute_edit(a, 0, b, 0) << ", replay of alignment: " << replay(a, b, ops) << "\n";
cout << "LCS: " << lcs_string(a, b) << "\n";
cout << "shortest common supersequence: " << shortest_common_supersequence(a, b) << "\n";
cout << "LCS avoiding \"ea\": " << lcs_avoiding(a, b, "ea") << "\n";
return 0;
}Running it gives this output:
a=lean b=lane cost=2
M l
D e
M a
M n
I e
rows version: 2
brute force: 2, replay of alignment: 2
LCS: lan
shortest common supersequence: leane
LCS avoiding "ea": 3The replay function walks the alignment and adds up its cost. If the alignment does not use both strings exactly, it returns -1. The brute force checker is only for strings of length 5 or less, because it tries every first operation without memory and its running time grows exponentially.
The same functions were also tested on random inputs in a separate test program that I wrote for this lesson. It checked 3000 random pairs of length 0 to 5 for edit distance (against brute force), 3000 pairs for LCS and the supersequence (length and subsequence checks), 3000 pairs for the forbidden-word LCS (against a brute force over all subsets), and 400 binary pairs for the supersequence length (against a brute force over all binary strings). The rolling-row versions agreed with the full tables on 20000 random pairs of length up to 11.
Here is a Python version of the LCS length. It is short and useful for reading the recurrence:
Its output:
lean lane 3 5
abcde ace 3 5
abc xyz 0 6Worked original problem: the weighted typo budget
A spell checker for product names counts a typo as a cost, not as a yes or no. Vowels are easy to drop when typing fast, so deleting or inserting a vowel is cheap. Other letters cost more. Replacing a letter with a nearby one in the alphabet costs less than replacing it with a distant one, up to a cap of 3.
Statement. You are given two lowercase strings a and b. Deleting a letter c from a, or inserting a letter c into a to match b, costs 1 if c is a vowel (a, e, i, o, u) and 2 otherwise. Replacing a letter x by a letter y costs 0 if x equals y, otherwise min(3, |x - y|), where letters are compared by their position in the alphabet (a is 0, z is 25). Find the minimum total cost, and print one optimal sequence of operations.
Input. Two lines, a and then b. Each has at most 2000 letters. Either line may be empty.
Output. The minimum cost on the first line. Then one line per operation, in order from the start of the strings: M c for a matched letter c, S x y for replacing x by y, D c for deleting c from a, and I c for inserting c from b. The alignment is not always unique, so a checker must replay it and accept any optimal one.
Example. For lean and lane the answer is 2 (deleting e and inserting e cost 1 each). The program output above is a correct answer.
Solution. The function weighted_edit is the solution. It fills the table from the base cases in time O(n * m), then walks back to build the operations. The program printed the operations, and replay confirmed that they cost 2. Each cell is checked against the three neighbours, so the table has all the information the walk needs.
Limits. With n and m up to 2000 the table has about 4 million cells. Each cell is one integer, so the full table is about 16 MB with 4-byte integers. That is fine for one test. If the program only needs the cost, the rolling-row version uses two rows.
Complexity
Time is O(n * m) for every variant. Memory is O(n * m) when the alignment or the LCS string is rebuilt from the full table, and O(m) for the cost only. The forbidden-word LCS takes O(n * m * |t|) time and memory with this table, where |t| is the length of the forbidden word.
Common mistakes
Missing base case. Without the first row and column, the empty prefix costs nothing. I ran a copy of the code with those two loops removed. It printed BUGGY edit("","ab")=0, where the correct cost is 3 (two insertions cost 1 for a and 2 for b). The same copy crashed with exit code 139, a segmentation fault, on edit("ab",""). The backtrack then read b[-1], a position before the start of b, because the table no longer matched the costs. If your program crashes on an empty input, check the base cases first.
Using the unit-cost shortcut. The formula n + m - 2 * LCS gives the edit cost only when every indel costs 1 and replacement is forbidden. For abc and xyz it gives 3 + 3 - 2 * 0 = 6. The task answer is 9, because each position pays a replacement of 3 instead of a deletion and an insertion. Check the formula against the brute force before you trust it.
Rolling rows with an alignment. The rolling-row function returns the right cost, but it has no way to print the operations. If you need the alignment, keep the table or use a linear-space method.
Forbidden words checked at the end. Testing the final string for the forbidden word is wrong, because the common subsequence can be stopped too late. The automaton state must be part of the table, and a step that reaches the full length of the forbidden word must be refused.
Empty input in the brute force. The checker must accept empty strings, because the base cases are the first things a test should cover.
Checklist
- Write the base cases first: the empty prefix against the other string.
- Write the recurrence in words, then in code, and check each of the three neighbours.
- Keep deletion and insertion costs separate when they differ.
- Run every new function against the brute force checker on strings of length 5 or less, and include the empty string.
- Use rolling rows only when you do not need the alignment.
- For a forbidden word, put the automaton state in the table.
- Do not reuse the unit-cost formula when the costs are weighted.
Practice problems
Practice 1: one deletion
Compute the weighted edit cost from abc to ab with the task costs, and give the operations.
Hint: the only difference is one character at the end, and it is not a vowel.
Show the answer
Cost 2. Operations: M a, M b, D c. The deleted c is not a vowel, so it costs 2.
Practice 2: supersequence by hand
Find a shortest common supersequence of abc and bd. Give its length and check it.
Hint: compute the LCS first. Its length gives the answer through n + m - LCS.
Show the answer
The LCS is b, so the length is 3 + 2 - 1 = 4. Both abdc and abcd are valid answers. Each contains abc and bd as subsequences. The program prints abdc.
Practice 3: forbidden word
Find the longest common subsequence of aab and aab that does not contain aa as a substring.
Hint: the full string aab contains aa, so look at the subsequences of length 2.
Show the answer
The answer is 2. The subsequence ab is common and does not contain aa. No common subsequence of length 3 avoids aa, because the only one is aab itself. The program lcs_avoiding("aab", "aab", "aa") prints 2.
Practice 4: rolling rows
Write a function that returns the LCS length with two rows, and check it against the full table on random strings.
Hint: the current row depends on the previous row only. Copy the current row into the previous row after each step, or swap them.
Show the answer
Use this code and compare with lcs_table(a, b).back().back() on random strings of length up to 11. In the lesson's check of 20000 random pairs, the rolling version had zero mismatches.
int lcs_rows(const string& a, const 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++) {
cur[0] = 0;
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = max(prev[j], cur[j - 1]);
}
swap(prev, cur);
}
return prev[m];
}Practice 5: why rows cannot rebuild
Explain in two sentences why the rolling-row function cannot print the alignment.
Hint: think about what the backtrack needs at each step.
Show the answer
The backtrack starts at the last cell and needs the earlier rows to decide each step. The rolling version overwrites those rows, so the choices are lost. You need the full table, or a linear-space method that recomputes parts of the table.
Summary
Edit distance, LCS and the shortest common supersequence all fill a table of prefix answers from three neighbours. Base cases come first. A table that only keeps two rows gives the number, not the alignment. A forbidden word needs its automaton state inside the table. Check every new function against a brute force program on tiny inputs before you trust it on large ones.