⚙️AlgorithmIntermediate

Edit Distance

Key Points

•
Edit distance (Levenshtein distance) measures the minimum number of inserts, deletes, and replaces needed to turn one string into another.
•
Dynamic programming solves edit distance by filling a (n+1) by (m+1) table where each cell represents the best cost for two prefixes.
•
The core recurrence takes the minimum of insert, delete, and replace transitions plus a match cost of 0 or replace cost of 1.
•
Base cases are the cost to turn an empty string into a prefix (all inserts) or a prefix into empty (all deletes).
•
Time complexity is O(nm) and space is O(nm), but space can be reduced to O(min(n, m)) with a rolling array.
•
You can reconstruct the actual edit script by storing parent moves and backtracking from the table’s bottom-right cell.
•
When a maximum distance k is known, banded DP reduces work to O(k · min(n, m)) and can early-exit if the distance exceeds k.
•
Weighted variants change the costs of insert/delete/replace to model different applications (e.g., keyboard typos vs. omissions).

Prerequisites

→String indexing and slicing — The DP states and transitions operate on prefixes; understanding indices prevents off-by-one errors.
→2D dynamic programming basics — Edit distance is a classic 2D DP problem with overlapping subproblems and optimal substructure.
→Time and space complexity — Choosing between full-table DP, rolling arrays, and banded DP requires analyzing O(nm) vs. O(k·n) trade-offs.
→Minimum/argmin reasoning — Transitions select the minimum of several options; understanding tie-breaking helps in reconstruction.
→Basic recursion/iteration — The DP recurrence is a bottom-up translation of a natural recursive definition.

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Imagine fixing a typo-laden text so it exactly matches the original. Every time you insert a missing letter, delete an extra one, or replace a wrong character, you perform an operation. How many operations are needed if you always fix in the smartest possible way? Concept: Edit distance, also called Levenshtein distance, formalizes this idea by defining the minimum number of inserts, deletes, and replaces required to transform one string into another. The standard solution uses dynamic programming: we consider all prefixes of both strings and build up the answer from smaller subproblems. We fill a grid where row i and column j store the best cost to transform the first i characters of s into the first j characters of t. Example: If s = "kitten" and t = "sitting", the distance is 3: replace 'k'→'s', replace 'e'→'i', and insert 'g'. This approach not only tells us the number (3) but can also reconstruct the exact sequence of edits that achieves this minimum. The DP method runs in O(nm) time for strings of lengths n and m, and common engineering optimizations reduce memory to O(min(n, m)).

02Intuition & Analogies

Hook: Think of two LEGO sculptures: one you built (s) and another you want (t). You are allowed three moves: add a brick (insert), remove a brick (delete), or swap a brick’s color (replace). What’s the shortest sequence of moves to get from yours to the target? Concept: If we compare the sculptures from the base up, we can decide, at each height, whether to add, remove, or recolor to keep progress minimal. Likewise, edit distance compares prefixes of two strings. Each cell in the DP table answers: if I’ve already matched the first i letters of s to the first j letters of t, what is the smallest cost so far? We only need to consider the three moves that could produce this cell: come from left (insert in s), from above (delete from s), or from diagonal (match/replace the last character). Example: Aligning "abc" to "adc" feels like deciding at the second letter: keep 'b' and change to 'd' (a replace), which is a single move. The DP table captures this by taking the diagonal neighbor and adding 0 if letters match or 1 if they differ. By pushing this local choice across the grid, we assemble the globally optimal plan.

03Formal Definition

Hook: To reason about correctness, we need a precise statement of the subproblem and recurrence. Concept: Let s and t be strings of lengths n and m. Define dp[i][j] as the minimum number of operations to transform the prefix s[1..i] into t[1..j] using insertions, deletions, and substitutions (all with unit cost). Base conditions: dp[0][j] = j (insert j letters) and dp[i][0] = i (delete i letters). The recurrence is dp[i][j] = min( dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + [s[i] != t[j]] ), where [·] is 1 if the predicate is true and 0 otherwise. Example: If s = "ab" and t = "acb", then dp[2][3] is the min of inserting 'b' at the end, deleting something earlier, or replacing/matching the last char; the optimal path realizes two edits overall. This DP is known as the Wagner–Fischer algorithm, and it computes the Levenshtein metric, which satisfies non-negativity, identity, symmetry, and triangle inequality. Space can be reduced because each row depends only on the previous row.

04When to Use

Hook: Whenever you need to say “how similar are these two strings?” consider edit distance. Concept: Use standard O(nm) DP when n·m is comfortably small (e.g., up to ~10^7 operations in optimized C++), or when you must reconstruct the exact edit script. In competitive programming at CF 1300–1700, typical inputs are small-to-medium or require just the distance. If memory is tight, prefer the rolling-array version that stores only two rows. If the task includes a known upper bound k on the allowed distance (e.g., accept if distance ≤ k), use banded DP/Ukkonen’s idea, which restricts work to a diagonal band of width 2k+1 and early-exits if all candidates exceed k. Example use cases: spell-checkers (closest dictionary word), diff tools (minimal set of edits), DNA/protein alignment (with possibly non-unit weights), fuzzy search/autocomplete (find near-matches), and text normalization pipelines.

⚠️Common Mistakes

Hook: Most wrong answers come from tiny off-by-one errors that snowball. Concept: Common pitfalls include mixing 0-based and 1-based indices while filling dp, forgetting base cases dp[0][j] = j and dp[i][0] = i, or using the wrong cost for a match (should add 0 on diagonal when s[i-1] == t[j-1]). Another frequent issue is memory: allocating an (n+1)×(m+1) table for very large strings causes MLE; fix by using two rows or ensuring the shorter string defines the row dimension. In banded DP, errors often come from computing the j-range incorrectly (clip to [0, m]) or failing to set out-of-band cells to +∞. For path reconstruction, a non-deterministic tie-break can yield different but still optimal scripts; if an exact script is judged, define a consistent priority (e.g., diagonal, then delete, then insert). Example: A subtle bug is updating a single rolling array left-to-right without keeping the previous dp[j-1] from the previous row (you need both prev[j] and curr[j-1]); otherwise, you mix states from the same row and corrupt the recurrence.

Key Formulas

Base Cases

d p [0] [j] = j, d p [i] [0] = i

Explanation: Transforming an empty string to the first j characters requires j insertions; transforming the first i characters to empty requires i deletions. These initialize the DP table's first row and column.

Levenshtein Recurrence

d p [i] [j] = min {d p [i] [j - 1] + 1, d p [i - 1] [j] + 1, d p [i - 1] [j - 1] + 1_{{s_{i} \neq = t_{j}}}}

Explanation: The best way to form t[1..j] from s[1..i] is to insert $t_{j}$ (left), delete $s_{i}$ (up), or match/replace $s_{i}$ to $t_{j}$ (diagonal). Matching adds 0; replacing adds 1.

Time Complexity

T (n, m) = O (nm)

Explanation: Filling an (n+1) by (m+1) table performs constant work per cell. The overall time grows proportional to the product of the string lengths.

Space Complexity

S (n, m) = O (nm) or O (min {n, m})

Explanation: Storing the whole table uses O(nm) memory. If only the distance is needed, a rolling array over the shorter string reduces memory to linear in min(n, m).

Weighted Edit Distance

d p [i] [j] = ⎩ ⎨ ⎧ j i min {d p [i] [j - 1] + c_{in s}, d p [i - 1] [j] + c_{d e l}, d p [i - 1] [j - 1] + c_{re p} (s_{i}, t_{j})} i = 0 j = 0 otherwise

Explanation: A generalized form where insertions, deletions, and replacements have custom costs. Set $c_{re p}$ (x,y)=0 if $x = y;$ otherwise use the mismatch penalty.

Insert/Delete Only

D_{ins,del} (s, t) = n + m - 2 LCS (s, t)

Explanation: If substitutions are disallowed, the minimum edits equal the total characters not part of any common subsequence. This connects edit distance to LCS.

Banded DP Complexity

T_{band} (n, m, k) = O ((n + m) k)

Explanation: If the optimal path stays within a diagonal band of width 2k+1, we compute only O(k) cells per row/column, yielding near-linear time in string length for small k.

Triangle Inequality

d (s, u) \leq d (s, t) + d (t, u)

Explanation: Levenshtein distance is a metric; composing optimal (or near-optimal) edit scripts from $s \to t$ and $t \to u$ gives an upper bound on $s \to u$ .

Complexity Analysis

The classic Wagner–Fischer dynamic programming algorithm fills an (n+1) by (m+1) table, where n =

∣ s ∣

and m =

∣ t ∣

. Each cell dp[i][j] is computed from three neighbors in O(1) time, so the total time is O(nm). This bound is tight in the worst case because the algorithm must consider all prefix pairs to account for interleaved insertions, deletions, and substitutions. The naive memory footprint is O(nm) integers, which can be high for large inputs (e.g., 10^5 × 10^5 is infeasible). If only the final distance is required, we can reduce space to O(min(n, m)) by keeping only the previous and current rows (rolling array). This works because dp[i][j] depends only on row i and i−1. With reconstruction of an edit script, we usually need O(nm) space for parent pointers, although Hirschberg-style divide-and-conquer ideas (common in sequence alignment) can reconstruct one optimal alignment with O(min(n, m)) extra space at the cost of more passes. When a maximum distance k is known (e.g., accept if

d i s t an ce \leq k

), banded DP limits computation to columns j ∈ [i−k, i+k], yielding O(k·min(n, m)) space and roughly O((n+m)k) time; this can offer orders-of-magnitude speedups for small k. However, banding may fail to detect

d i s t an ces > k

early unless it tracks and prunes states exceeding k. In practice, careful constant-factor optimizations (tight loops, small integer types when safe) are important for passing time limits in competitive programming.

Code Examples

Classic O(nm) DP with Edit Script Reconstruction

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Reconstructable Levenshtein distance (unit costs). Returns distance and prints one optimal edit script.
5 // Operations are reported in a human-readable form.
6 
7 int main() {
8     ios::sync_with_stdio(false);
9     cin.tie(nullptr);
10 
11     string s, t;
12     // Example input (you can replace with cin >> s >> t;)
13     s = "kitten";
14     t = "sitting";
15 
16     int n = (int)s.size();
17     int m = (int)t.size();
18 
19     // dp[i][j] = edit distance between s[0..i-1] and t[0..j-1]
20     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
21     // parent[i][j]: 0 = diag (match/replace), 1 = left (insert), 2 = up (delete)
22     vector<vector<unsigned char>> parent(n + 1, vector<unsigned char>(m + 1, 0));
23 
24     for (int i = 0; i <= n; ++i) {
25         dp[i][0] = i;
26         if (i > 0) parent[i][0] = 2; // came from up (delete)
27     }
28     for (int j = 0; j <= m; ++j) {
29         dp[0][j] = j;
30         if (j > 0) parent[0][j] = 1; // came from left (insert)
31     }
32 
33     for (int i = 1; i <= n; ++i) {
34         for (int j = 1; j <= m; ++j) {
35             int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
36             int best = dp[i - 1][j - 1] + cost; // diagonal: match/replace
37             unsigned char move = 0; // diag
38 
39             int cand = dp[i][j - 1] + 1; // left: insert t[j-1]
40             if (cand < best) { best = cand; move = 1; }
41             cand = dp[i - 1][j] + 1; // up: delete s[i-1]
42             if (cand < best) { best = cand; move = 2; }
43 
44             dp[i][j] = best;
45             parent[i][j] = move;
46         }
47     }
48 
49     cout << "Edit distance: " << dp[n][m] << "\n";
50 
51     // Traceback to reconstruct one optimal edit script
52     vector<string> script;
53     int i = n, j = m;
54     while (i > 0 || j > 0) {
55         unsigned char mv = parent[i][j];
56         if (i > 0 && j > 0 && mv == 0) {
57             if (s[i - 1] == t[j - 1]) {
58                 // Match, no operation needed (optional to record)
59                 // script.push_back("Match '" + string(1, s[i-1]) + "' at position " + to_string(i-1));
60             } else {
61                 script.push_back("Replace position " + to_string(i - 1) + " ('" + string(1, s[i - 1]) + "') with '" + string(1, t[j - 1]) + "'");
62             }
63             --i; --j;
64         } else if (j > 0 && mv == 1) {
65             script.push_back("Insert '" + string(1, t[j - 1]) + "' at position " + to_string(i));
66             --j;
67         } else { // mv == 2
68             script.push_back("Delete '" + string(1, s[i - 1]) + "' at position " + to_string(i - 1));
69             --i;
70         }
71     }
72     reverse(script.begin(), script.end());
73 
74     cout << "One optimal edit script (" << script.size() << " steps):\n";
75     for (auto &line : script) cout << "- " << line << "\n";
76 
77     return 0;
78 }
79

Builds the full DP table with base cases, applies the standard recurrence, and stores parent pointers to backtrack. The traceback yields one optimal sequence of operations. Deterministic tie-breaking (prefer diagonal, then insert, then delete) ensures reproducibility.

Time: O(nm)Space: O(nm)

Space-Optimized Edit Distance (Two-Row Rolling Array)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes Levenshtein distance with O(min(n,m)) space.
5 int levenshtein_distance_space_optimized(const string &s, const string &t) {
6     int n = (int)s.size();
7     int m = (int)t.size();
8 
9     // Ensure t is the shorter to minimize memory
10     if (m > n) return levenshtein_distance_space_optimized(t, s);
11 
12     vector<int> prev(m + 1), curr(m + 1);
13     iota(prev.begin(), prev.end(), 0); // prev[j] = j
14 
15     for (int i = 1; i <= n; ++i) {
16         curr[0] = i; // deleting i characters to reach empty t
17         for (int j = 1; j <= m; ++j) {
18             int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
19             // Transitions: insert (curr[j-1]+1), delete (prev[j]+1), replace/match (prev[j-1]+cost)
20             curr[j] = min({ curr[j - 1] + 1, prev[j] + 1, prev[j - 1] + cost });
21         }
22         swap(prev, curr);
23     }
24     return prev[m];
25 }
26 
27 int main() {
28     ios::sync_with_stdio(false);
29     cin.tie(nullptr);
30 
31     string s = "algorithm", t = "altruistic";
32     cout << levenshtein_distance_space_optimized(s, t) << "\n";
33     return 0;
34 }
35

Keeps only the previous and current DP rows. The recurrence is identical, but memory drops to linear in the shorter string’s length. Swapping rows at the end of each iteration preserves correctness.

Time: O(nm)Space: O(min(n, m))

Banded DP with Cutoff k (Early Exit if Distance > k)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Returns edit distance if <= k, else -1. Banded DP around the main diagonal.
5 int bounded_edit_distance(const string &s, const string &t, int k) {
6     int n = (int)s.size();
7     int m = (int)t.size();
8 
9     // Quick length-based pruning
10     if (abs(n - m) > k) return -1;
11 
12     const int INF = 1e9;
13     // The band width is 2k+1; we need only two rows of that width.
14     // We map column j to band index b = j - (i - k), where j in [max(0,i-k), min(m,i+k)].
15     vector<int> prev(2 * k + 3, INF), curr(2 * k + 3, INF);
16 
17     // Initialize row i=0: j in [0, min(m, k)]
18     for (int j = 0; j <= min(m, k); ++j) {
19         int b = j - (0 - k); // = j + k
20         prev[b] = j; // dp[0][j] = j
21     }
22 
23     for (int i = 1; i <= n; ++i) {
24         fill(curr.begin(), curr.end(), INF);
25         int jlo = max(0, i - k);
26         int jhi = min(m, i + k);
27         for (int j = jlo; j <= jhi; ++j) {
28             int b = j - (i - k); // band index for (i,j)
29             // Diagonal (i-1,j-1)
30             if (j - 1 >= max(0, i - 1 - k) && j - 1 <= min(m, i - 1 + k)) {
31                 int bd = (j - 1) - ((i - 1) - k);
32                 int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
33                 curr[b] = min(curr[b], prev[bd] + cost);
34             }
35             // Left (i, j-1): insert
36             if (j - 1 >= jlo) {
37                 int bl = (j - 1) - (i - k);
38                 curr[b] = min(curr[b], curr[bl] + 1);
39             }
40             // Up (i-1, j): delete
41             if (j >= max(0, i - 1 - k) && j <= min(m, i - 1 + k)) {
42                 int bu = j - ((i - 1) - k);
43                 curr[b] = min(curr[b], prev[bu] + 1);
44             }
45         }
46         // Early abort if the entire band is > k
47         int bestRow = *min_element(curr.begin(), curr.end());
48         if (bestRow > k) return -1;
49         swap(prev, curr);
50     }
51 
52     int j = m;
53     if (j < max(0, n - k) || j > min(m, n + k)) return -1;
54     int b = j - (n - k);
55     return prev[b] <= k ? prev[b] : -1;
56 }
57 
58 int main() {
59     ios::sync_with_stdio(false);
60     cin.tie(nullptr);
61 
62     string s = "intention", t = "execution";
63     int k = 5;
64     cout << bounded_edit_distance(s, t, k) << "\n"; // prints 5, or -1 if > k
65     return 0;
66 }
67

Restricts computation to a diagonal band of width 2k+1, which is sufficient if the optimal path deviates by at most k from the diagonal. It aborts early when all states in the current row exceed k, returning -1 to indicate distance > k.

Time: O((n + m) · k)Space: O(k)

Weighted Edit Distance (Custom Costs for Insert/Delete/Replace)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes minimum edit cost with custom operation costs.
5 // c_rep(x,y) = 0 if x==y, else repCost.
6 long long weighted_edit_distance(const string &s, const string &t, int insCost, int delCost, int repCost) {
7     int n = (int)s.size();
8     int m = (int)t.size();
9     vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
10 
11     for (int i = 0; i <= n; ++i) dp[i][0] = 1LL * i * delCost;
12     for (int j = 0; j <= m; ++j) dp[0][j] = 1LL * j * insCost;
13 
14     for (int i = 1; i <= n; ++i) {
15         for (int j = 1; j <= m; ++j) {
16             long long costRep = (s[i - 1] == t[j - 1]) ? 0 : repCost;
17             dp[i][j] = min({
18                 dp[i][j - 1] + insCost,      // insert t[j-1]
19                 dp[i - 1][j] + delCost,      // delete s[i-1]
20                 dp[i - 1][j - 1] + costRep   // match or replace
21             });
22         }
23     }
24     return dp[n][m];
25 }
26 
27 int main() {
28     ios::sync_with_stdio(false);
29     cin.tie(nullptr);
30 
31     string s = "color", t = "colour";
32     int ins = 1, del = 1, rep = 2; // Heavier penalty for replacement
33     cout << weighted_edit_distance(s, t, ins, del, rep) << "\n";
34     return 0;
35 }
36

Generalizes the recurrence to different operation costs. This is useful when substitutions are less likely than insertions/deletions or when domain knowledge suggests asymmetric penalties.

Time: O(nm)Space: O(nm)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Reconstructable Levenshtein distance (unit costs). Returns distance and prints one optimal edit script.
5	// Operations are reported in a human-readable form.
6
7	int main() {
8	ios::sync_with_stdio(false);
9	cin.tie(nullptr);
10
11	string s, t;
12	// Example input (you can replace with cin >> s >> t;)
13	s = "kitten";
14	t = "sitting";
15
16	int n = (int)s.size();
17	int m = (int)t.size();
18
19	// dp[i][j] = edit distance between s[0..i-1] and t[0..j-1]
20	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
21	// parent[i][j]: 0 = diag (match/replace), 1 = left (insert), 2 = up (delete)
22	vector<vector<unsigned char>> parent(n + 1, vector<unsigned char>(m + 1, 0));
23
24	for (int i = 0; i <= n; ++i) {
25	dp[i][0] = i;
26	if (i > 0) parent[i][0] = 2; // came from up (delete)
27	}
28	for (int j = 0; j <= m; ++j) {
29	dp[0][j] = j;
30	if (j > 0) parent[0][j] = 1; // came from left (insert)
31	}
32
33	for (int i = 1; i <= n; ++i) {
34	for (int j = 1; j <= m; ++j) {
35	int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
36	int best = dp[i - 1][j - 1] + cost; // diagonal: match/replace
37	unsigned char move = 0; // diag
38
39	int cand = dp[i][j - 1] + 1; // left: insert t[j-1]
40	if (cand < best) { best = cand; move = 1; }
41	cand = dp[i - 1][j] + 1; // up: delete s[i-1]
42	if (cand < best) { best = cand; move = 2; }
43
44	dp[i][j] = best;
45	parent[i][j] = move;
46	}
47	}
48
49	cout << "Edit distance: " << dp[n][m] << "\n";
50
51	// Traceback to reconstruct one optimal edit script
52	vector<string> script;
53	int i = n, j = m;
54	while (i > 0 \|\| j > 0) {
55	unsigned char mv = parent[i][j];
56	if (i > 0 && j > 0 && mv == 0) {
57	if (s[i - 1] == t[j - 1]) {
58	// Match, no operation needed (optional to record)
59	// script.push_back("Match '" + string(1, s[i-1]) + "' at position " + to_string(i-1));
60	} else {
61	script.push_back("Replace position " + to_string(i - 1) + " ('" + string(1, s[i - 1]) + "') with '" + string(1, t[j - 1]) + "'");
62	}
63	--i; --j;
64	} else if (j > 0 && mv == 1) {
65	script.push_back("Insert '" + string(1, t[j - 1]) + "' at position " + to_string(i));
66	--j;
67	} else { // mv == 2
68	script.push_back("Delete '" + string(1, s[i - 1]) + "' at position " + to_string(i - 1));
69	--i;
70	}
71	}
72	reverse(script.begin(), script.end());
73
74	cout << "One optimal edit script (" << script.size() << " steps):\n";
75	for (auto &line : script) cout << "- " << line << "\n";
76
77	return 0;
78	}
79

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes Levenshtein distance with O(min(n,m)) space.
5	int levenshtein_distance_space_optimized(const string &s, const string &t) {
6	int n = (int)s.size();
7	int m = (int)t.size();
8
9	// Ensure t is the shorter to minimize memory
10	if (m > n) return levenshtein_distance_space_optimized(t, s);
11
12	vector<int> prev(m + 1), curr(m + 1);
13	iota(prev.begin(), prev.end(), 0); // prev[j] = j
14
15	for (int i = 1; i <= n; ++i) {
16	curr[0] = i; // deleting i characters to reach empty t
17	for (int j = 1; j <= m; ++j) {
18	int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
19	// Transitions: insert (curr[j-1]+1), delete (prev[j]+1), replace/match (prev[j-1]+cost)
20	curr[j] = min({ curr[j - 1] + 1, prev[j] + 1, prev[j - 1] + cost });
21	}
22	swap(prev, curr);
23	}
24	return prev[m];
25	}
26
27	int main() {
28	ios::sync_with_stdio(false);
29	cin.tie(nullptr);
30
31	string s = "algorithm", t = "altruistic";
32	cout << levenshtein_distance_space_optimized(s, t) << "\n";
33	return 0;
34	}
35

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Returns edit distance if <= k, else -1. Banded DP around the main diagonal.
5	int bounded_edit_distance(const string &s, const string &t, int k) {
6	int n = (int)s.size();
7	int m = (int)t.size();
8
9	// Quick length-based pruning
10	if (abs(n - m) > k) return -1;
11
12	const int INF = 1e9;
13	// The band width is 2k+1; we need only two rows of that width.
14	// We map column j to band index b = j - (i - k), where j in [max(0,i-k), min(m,i+k)].
15	vector<int> prev(2 * k + 3, INF), curr(2 * k + 3, INF);
16
17	// Initialize row i=0: j in [0, min(m, k)]
18	for (int j = 0; j <= min(m, k); ++j) {
19	int b = j - (0 - k); // = j + k
20	prev[b] = j; // dp[0][j] = j
21	}
22
23	for (int i = 1; i <= n; ++i) {
24	fill(curr.begin(), curr.end(), INF);
25	int jlo = max(0, i - k);
26	int jhi = min(m, i + k);
27	for (int j = jlo; j <= jhi; ++j) {
28	int b = j - (i - k); // band index for (i,j)
29	// Diagonal (i-1,j-1)
30	if (j - 1 >= max(0, i - 1 - k) && j - 1 <= min(m, i - 1 + k)) {
31	int bd = (j - 1) - ((i - 1) - k);
32	int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
33	curr[b] = min(curr[b], prev[bd] + cost);
34	}
35	// Left (i, j-1): insert
36	if (j - 1 >= jlo) {
37	int bl = (j - 1) - (i - k);
38	curr[b] = min(curr[b], curr[bl] + 1);
39	}
40	// Up (i-1, j): delete
41	if (j >= max(0, i - 1 - k) && j <= min(m, i - 1 + k)) {
42	int bu = j - ((i - 1) - k);
43	curr[b] = min(curr[b], prev[bu] + 1);
44	}
45	}
46	// Early abort if the entire band is > k
47	int bestRow = *min_element(curr.begin(), curr.end());
48	if (bestRow > k) return -1;
49	swap(prev, curr);
50	}
51
52	int j = m;
53	if (j < max(0, n - k) \|\| j > min(m, n + k)) return -1;
54	int b = j - (n - k);
55	return prev[b] <= k ? prev[b] : -1;
56	}
57
58	int main() {
59	ios::sync_with_stdio(false);
60	cin.tie(nullptr);
61
62	string s = "intention", t = "execution";
63	int k = 5;
64	cout << bounded_edit_distance(s, t, k) << "\n"; // prints 5, or -1 if > k
65	return 0;
66	}
67

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes minimum edit cost with custom operation costs.
5	// c_rep(x,y) = 0 if x==y, else repCost.
6	long long weighted_edit_distance(const string &s, const string &t, int insCost, int delCost, int repCost) {
7	int n = (int)s.size();
8	int m = (int)t.size();
9	vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
10
11	for (int i = 0; i <= n; ++i) dp[i][0] = 1LL * i * delCost;
12	for (int j = 0; j <= m; ++j) dp[0][j] = 1LL * j * insCost;
13
14	for (int i = 1; i <= n; ++i) {
15	for (int j = 1; j <= m; ++j) {
16	long long costRep = (s[i - 1] == t[j - 1]) ? 0 : repCost;
17	dp[i][j] = min({
18	dp[i][j - 1] + insCost, // insert t[j-1]
19	dp[i - 1][j] + delCost, // delete s[i-1]
20	dp[i - 1][j - 1] + costRep // match or replace
21	});
22	}
23	}
24	return dp[n][m];
25	}
26
27	int main() {
28	ios::sync_with_stdio(false);
29	cin.tie(nullptr);
30
31	string s = "color", t = "colour";
32	int ins = 1, del = 1, rep = 2; // Heavier penalty for replacement
33	cout << weighted_edit_distance(s, t, ins, del, rep) << "\n";
34	return 0;
35	}
36