Dynamic Programming 2: Real Problems with Edit Distance, LCS and Knapsack

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8 and the diff comparison with Git 2.54.

Guess First

A user types "dnue" into the Bookstore search box. Our catalog has "Dune". We measure the difference between two words as the fewest letter insertions, deletions and substitutions needed to turn one into the other (edit distance). What is the distance between "dnue" and "dune"? Two letters swapped places, so 1? And if the code that computes it scans the 10,000 titles in our catalog on every search, how long does that take?

A Two-Dimensional State: A Table of Prefixes

In the 21st post of the series the state was a single number. When comparing two strings the state is two-dimensional: d[i, j] is the lowest cost of turning the first i letters of a into the first j letters of b. Let's read it with the five-step recipe. Transition: we look at the i-th letter of a and the j-th letter of b. If they are equal we move on for free (d[i-1, j-1]). Otherwise there are three options: substitute the letter (d[i-1, j-1] + 1), delete from a (d[i-1, j] + 1), insert b's letter (d[i, j-1] + 1); we take the smallest. Base case: to turn into the empty string delete everything (d[i, 0] = i), to turn the empty string into something insert everything (d[0, j] = j). Order: row by row, left to right. Answer: d[n, m].

// d[i, j] = edits to turn the first i chars of a into the first j chars of b.
public static int[,] Table(string a, string b)
{
    int[,] d = new int[a.Length + 1, b.Length + 1];
    for (int i = 0; i <= a.Length; i++) d[i, 0] = i; // delete everything
    for (int j = 0; j <= b.Length; j++) d[0, j] = j; // insert everything
    for (int i = 1; i <= a.Length; i++)
    {
        for (int j = 1; j <= b.Length; j++)
        {
            int replace = d[i - 1, j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1);
            int delete = d[i - 1, j] + 1;
            int insert = d[i, j - 1] + 1;
            d[i, j] = Math.Min(replace, Math.Min(delete, insert));
        }
    }

    return d;
}

This is the Levenshtein distance, named after Vladimir Levenshtein's 1965 work. The table for the opening question:

      ε d u n e
   ε  0 1 2 3 4
   d  1 0 1 2 3
   n  2 1 1 1 2
   u  3 2 1 2 2
   e  4 3 2 2 2
dnue -> dune: 2
kitten -> sitting: 3

The answer is 2, not 1. Levenshtein's three operations have no "swap two adjacent letters"; a swap counts as two substitutions, or a deletion plus an insertion. The variant that counts an adjacent transposition as a single operation is the Damerau-Levenshtein distance; since it is the most common typing mistake, it is often preferred for spelling suggestions. Which one you pick determines how close "Dune" counts for the query "dnue".

"Did You Mean?"

When a search returns nothing, we can suggest the catalog title with a small distance. We do not need the whole table: each row uses only the previous row, so two rows are enough. Moreover, if all we care about is "is it less than 2", we stop when the smallest value of a row exceeds the limit; no value after that row can get smaller:

// Only the previous row is needed: O(min(n, m)) memory, optional early exit.
public static int Levenshtein(string a, string b, int maxDistance = int.MaxValue)
{
    if (a.Length < b.Length) (a, b) = (b, a);
    if (a.Length - b.Length > maxDistance) return maxDistance + 1;

    int[] previous = new int[b.Length + 1];
    int[] current = new int[b.Length + 1];
    for (int j = 0; j <= b.Length; j++) previous[j] = j;
    for (int i = 1; i <= a.Length; i++)
    {
        current[0] = i;
        int rowMin = current[0];
        for (int j = 1; j <= b.Length; j++)
        {
            int cost = a[i - 1] == b[j - 1] ? 0 : 1;
            current[j] = Math.Min(previous[j - 1] + cost, Math.Min(previous[j] + 1, current[j - 1] + 1));
            rowMin = Math.Min(rowMin, current[j]);
        }

        if (rowMin > maxDistance) return maxDistance + 1; // cannot get better from here
        (previous, current) = (current, previous);
    }

    return previous[b.Length];
}

public static string? DidYouMean(string query, IEnumerable<string> titles, int maxDistance = 2)
{
    string q = query.Trim().ToLowerInvariant();
    return titles
        .Select(t => (Title: t, Distance: Levenshtein(q, t.ToLowerInvariant(), maxDistance)))
        .Where(x => x.Distance <= maxDistance)
        .OrderBy(x => x.Distance)
        .ThenBy(x => x.Title, StringComparer.Ordinal)
        .Select(x => x.Title)
        .FirstOrDefault();
}

pride and prejudise  -> Pride and Prejudice
frankenstien         -> Frankenstein
dun                  -> Dune
middlemrach          -> Middlemarch
harry potter         -> (no suggestion)

"harry potter" is not in our catalog and even the closest title is farther than 2; making no suggestion is better than making a silly one. There are two thresholds: if the length difference already exceeds maxDistance we never enter the table; inside the table we stop when an entire row exceeds the limit. I measured the effect on 10,000 random two-word titles:

[Benchmark(Baseline = true)]
public int FullTable() => _titles.Count(t => EditDistance.Table(Query, t)[Query.Length, t.Length] <= 2);

[Benchmark]
public int TwoRows() => _titles.Count(t => EditDistance.Levenshtein(Query, t) <= 2);

[Benchmark]
public int TwoRowsBounded() => _titles.Count(t => EditDistance.Levenshtein(Query, t, maxDistance: 2) <= 2);

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers.

| Method         | Mean        | Ratio | Allocated |
|--------------- |------------:|------:|----------:|
| FullTable      | 13,907.5 us |  1.00 |  16.95 MB |
| TwoRows        | 12,663.9 us |  0.91 |   1.97 MB |
| TwoRowsBounded |    666.3 us |  0.05 |    1.1 MB |

Switching to two rows barely changes the time but cuts allocations from 17 MB to 2 MB; the full table allocates an int[,] per title. The real gain comes from the early exit: 20 times. Most titles are very different from the query and get eliminated in the first few rows. The cost is O(n·m) for the full table; in practice the bounded version pays a small fraction of that. For larger catalogs even this is not enough; you need to narrow the candidates first with a structure like an n-gram index or a BK (Burkhard-Keller) tree and apply Levenshtein only to those.

LCS and the Basis of Diff Tools

The LCS (Longest Common Subsequence) is the longest subsequence two sequences have in common while keeping order; the elements do not have to be consecutive. The table is very similar to edit distance: if the elements are equal, one more than the diagonal neighbor; otherwise the larger of the top and left neighbors.

// len[i, j] = LCS length of a[..i] and b[..j].
public static int[,] Table<T>(IReadOnlyList<T> a, IReadOnlyList<T> b)
{
    EqualityComparer<T> eq = EqualityComparer<T>.Default;
    int[,] len = new int[a.Count + 1, b.Count + 1];
    for (int i = 1; i <= a.Count; i++)
        for (int j = 1; j <= b.Count; j++)
            len[i, j] = eq.Equals(a[i - 1], b[j - 1])
                ? len[i - 1, j - 1] + 1
                : Math.Max(len[i - 1, j], len[i, j - 1]);
    return len;
}

When the elements are lines, LCS becomes a diff tool: lines common to both files are "unchanged", lines in the first file but not in the LCS are "removed", lines in the second but not in the LCS are "added". We produce this by walking the table from the end back to the start:

// Walks the table back to produce a line diff: ' ' same, '-' removed, '+' added.
public static List<string> Diff(IReadOnlyList<string> oldLines, IReadOnlyList<string> newLines)
{
    int[,] len = Table(oldLines, newLines);
    List<string> result = [];
    int i = oldLines.Count, j = newLines.Count;
    while (i > 0 || j > 0)
    {
        if (i > 0 && j > 0 && oldLines[i - 1] == newLines[j - 1])
        {
            result.Add("  " + oldLines[--i]);
            j--;
        }
        else if (j > 0 && (i == 0 || len[i, j - 1] >= len[i - 1, j]))
        {
            result.Add("+ " + newLines[--j]);
        }
        else
        {
            result.Add("- " + oldLines[--i]);
        }
    }

    result.Reverse();
    return result;
}

Two versions of the Bookstore price list CSV (Comma-Separated Values): Dune's price changed and Dracula was added.

LCS length = 3
  isbn,title,price
- 9780441013593,Dune,18.99
+ 9780441013593,Dune,16.99
  9780141439518,Pride and Prejudice,9.99
+ 9780486411095,Dracula,7.25
  9780486282114,Frankenstein,6.50

I wrote the same two files to disk and asked Git too:

$ git -c core.pager=cat diff --no-index --no-color books-v1.csv books-v2.csv
diff --git a/books-v1.csv b/books-v2.csv
index 9f133c6..523b7d4 100644
--- a/books-v1.csv
+++ b/books-v2.csv
@@ -1,4 +1,5 @@
 isbn,title,price
-9780441013593,Dune,18.99
+9780441013593,Dune,16.99
 9780141439518,Pride and Prejudice,9.99
+9780486411095,Dracula,7.25
 9780486282114,Frankenstein,6.50

The lines are identical. According to Git's documentation the default diff algorithm is "myers": the algorithm from Eugene Myers' 1986 paper "An O(ND) Difference Algorithm and Its Variations". Our table spends O(n·m) time and memory; Myers' algorithm O((n + m)·D), where D is the number of differences. For two large files with few differences (a typical commit) D is small and the difference is dramatic. Git also offers algorithms that prioritize readability, like patience and histogram, through --diff-algorithm. The idea is the same: find the longest common subsequence; the rest is insertions and deletions.

0/1 Knapsack: Choosing Campaigns Under a Budget

The marketing team has a budget of 10 units and five candidate campaigns; each campaign has a cost and an expected extra revenue. Each campaign is either run or not (0/1); there are no half campaigns. Which selection maximizes revenue without exceeding the budget?

public sealed record Campaign(string Name, int Cost, int ExpectedRevenue);

// best[i, b] = best revenue using the first i campaigns with budget b. O(n * B).
public static (int Revenue, List<Campaign> Chosen) Solve(IReadOnlyList<Campaign> items, int budget)
{
    int n = items.Count;
    int[,] best = new int[n + 1, budget + 1];
    for (int i = 1; i <= n; i++)
    {
        Campaign c = items[i - 1];
        for (int b = 0; b <= budget; b++)
        {
            best[i, b] = best[i - 1, b];                                   // skip
            if (c.Cost <= b)
            {
                best[i, b] = Math.Max(best[i, b], best[i - 1, b - c.Cost] + c.ExpectedRevenue); // take
            }
        }
    }

    // Walk the table back to find which campaigns were chosen
    List<Campaign> chosen = [];
    for (int i = n, b = budget; i > 0; i--)
    {
        if (best[i, b] != best[i - 1, b])
        {
            chosen.Add(items[i - 1]);
            b -= items[i - 1].Cost;
        }
    }

    chosen.Reverse();
    return (best[n, budget], chosen);
}

Campaign[] campaigns =
[
    new("Newsletter", 1, 4), new("Podcast", 5, 15), new("Search ads", 5, 15),
    new("Book fair", 6, 17), new("Influencer", 4, 10),
];

DP: revenue=30, chosen=Podcast + Search ads
greedy by ratio: revenue=29, chosen=Newsletter + Podcast + Influencer

The greedy that picks in order of "most revenue per unit cost" takes the most efficient campaign (Newsletter, ratio 4) first and therefore misses the pair that fills the budget best: 29 against 30. This is the same story as the coins in the 20th post of the series: ratio order is optimal for fractional knapsack (when you can run half a campaign), not for 0/1. The cost is O(n·B); since B is the numeric value of the budget, this is called pseudo-polynomial. If the budget is in the millions in cents, the table is that big too.

Two Rows, Then One

Row i uses only row i-1; as with edit distance, two rows are enough. We can go one step further: a single array, but with the budget loop running backwards. Going backwards, best[b - c.Cost] is still the previous row's value, because smaller indexes have not been updated in this round yet:

// One row is enough if the budget loop runs backwards: each item is used at most once.
public static int SolveOneRow(IReadOnlyList<Campaign> items, int budget)
{
    int[] best = new int[budget + 1];
    foreach (Campaign c in items)
        for (int b = budget; b >= c.Cost; b--)
            best[b] = Math.Max(best[b], best[b - c.Cost] + c.ExpectedRevenue);
    return best[budget];
}

// Forward loop: an item can be taken again in the same pass (unbounded knapsack).
public static int SolveOneRowForward(IReadOnlyList<Campaign> items, int budget)
{
    int[] best = new int[budget + 1];
    foreach (Campaign c in items)
        for (int b = c.Cost; b <= budget; b++)
            best[b] = Math.Max(best[b], best[b - c.Cost] + c.ExpectedRevenue);
    return best[budget];
}

one row backwards=30, one row forwards=40

The forward loop says 40: running the Newsletter ten times (10 × 4). When the loop goes forward, best[b - c.Cost] has already been updated in this round, so it is a value that includes the same campaign; the campaign adds itself again and again. This is a sibling of the CountWays versus CountSequences difference from the previous post: a single change of direction turns the problem from 0/1 knapsack into unbounded knapsack. That is why the tests check the three versions against each other:

Test run summary: Passed!
  total: 13
  failed: 0
  succeeded: 13
  skipped: 0
  duration: 236ms

Closing the Series: Which Pattern When You See the Problem

Across 22 posts we wrote every structure ourselves first, then looked at its .NET counterpart, then saw where it pays off in a real project. Interview questions and real business problems usually arrive with a signal; recognize the signal and the right tool follows:

The most important row of the table is actually the one not written: most of the time the answer already exists in the BCL (Base Class Library). Dictionary, SortedSet, PriorityQueue, Array.Sort and BinarySearch are tested, optimized and maintained structures. We rewrote them in this series not to use them in production but to see their costs and be able to pick the right one. You can find the language of complexity in the Big-O and Complexity series, the collection APIs (Application Programming Interfaces) in the C# Collections series, and measuring in the BenchmarkDotNet post of the C# Advanced series.

Production Notes

Memory grows as O(n·m). The full edit distance table for two 10,000-character texts is 10⁸ cells, a 400 MB int[,]. If you only need the distance, switch to two rows; if you also need the alignment itself, there are linear-memory techniques like Hirschberg's, or Myers' algorithm.

Limit user input. If the "did you mean?" endpoint compares against the whole catalog on every call, a long query text turns directly into CPU (Central Processing Unit) cost. Put an upper bound on query length and use the bounded version.

Normalize before comparing. Case, whitespace and Turkish characters inflate the distance. Apply a single folding function like SearchKey.Fold from the 14th post of the series to both titles and queries; the distance between "Şu Çılgın Türkler" and "su cilgin turkler" should be 0.

Keep knapsack units small. If the budget is 1,000,000 in cents, the table has a million columns. Rounding costs to a meaningful unit (thousands of lira) keeps the table manageable; check the effect of rounding on the result with a test.

Common Pitfalls

Expecting Levenshtein to count a swap as one operation. It gives 2 for "dnue"; if you want an adjacent transposition to count as 1, write the Damerau variant and document which one you use.

Reversing the loop direction in one-row knapsack. The forward loop silently turns into unbounded knapsack and says 40 instead of 30 in our example. No exception; just a campaign plan that is impossible in reality.

Mixing up the index shift. The table is kept with one extra row and column (for the empty prefix); writing a[i] instead of a[i - 1] leads both to an IndexOutOfRangeException and to results shifted by one letter. Pin down small examples ("kitten" to "sitting" = 3) in tests.

Assuming a diff is independent of the definition of equality. A line ending difference (CRLF (Carriage Return + Line Feed) on Windows vs LF (Line Feed) on Unix) or trailing whitespace makes the whole file show as "changed". Normalize the lines before comparing, or define equality explicitly with an IEqualityComparer.

A Small Experiment

★☆☆ Write Damerau-Levenshtein (optimal string alignment) by adding adjacent transpositions to EditDistance.Table: if a[i-1] == b[j-2] && a[i-2] == b[j-1], d[i-2, j-2] + 1 is also an option. Is "dnue" to "dune" now 1?

★★☆ Extend Lcs.Diff to group consecutive changes into hunks with @@ -1,4 +1,5 @@ headers like git; add 3 lines of context and compare the output with git diff for the same files.

★★★ Add a second constraint to the knapsack: besides the budget, a capacity under which the team can run at most 3 campaigns. The state becomes three-dimensional (campaign, budget, count); solve it with the full table first, then see how many dimensions you can reduce to a single row.

With this post the "Algorithms and Data Structures" series is complete. From arrays to hash tables, from sorting to trees, from graphs to dynamic programming, we wrote every structure ourselves, measured it against its BCL counterpart and applied it to the Bookstore's real problems. The next step is your project: at the next slow endpoint, or the next "why does this code collapse at 10,000 records" question, look for which row of the table above you are facing.