Subproblems, strings, and search tricks

In Post 6 we built recursion and divide-and-conquer from first principles, learning to split problems into independent halves and combine the answers. This post takes those tools and points them at a harder class of problems: ones where the subproblems overlap, where strings refuse to be split cleanly, and where the naive search is too slow to matter. We work through seven design techniques, memoization and tabulation for overlapping subproblems, and four string transforms, all tested against a real English word list of 370,105 words. By the end, our Knuth-Morris-Pratt (KMP) matcher finds 560 occurrences of "tion" in a 20,000-word corpus in 0.00853 seconds, and the Fast Fourier Transform multiplies two 2000-coefficient polynomials in 0.00018 seconds, a thousandfold improvement over the schoolbook method.

The through-line for this post is the idea of a search budget. Every algorithm we meet is a way of spending fewer comparisons, fewer table cells, or fewer nodes to reach the same answer. The word list gives us a natural arena where those budgets matter, because a vocabulary of 370,105 words punishes any method that insists on looking at everything twice.

The word list

Our dataset is the dwyl/english-words collection on GitHub, about 4 MB of raw text holding one word per line. After cleaning, we have 370,105 unique lowercase words with no missing values and no duplicate lines. The vocabulary is large enough that search tricks matter, and natural enough that edit distances and common subsequences between words mean something.

The first thing we do is look at the shape of the data, because every later choice traces back to these observations. Word lengths are right-skewed: the median word has 9 letters, the mean sits at 9.44, and a long tail stretches past 15 letters up to a maximum of 31. The base rate of long words, defined as length 8 or more, is 0.736, which means random guessing is never a strong baseline for any classification we might attempt. Letter frequencies drop on a log scale, so rare letters like "q" and "z" become useful stress cases for pattern matching.

Figure 1 shows the word-length distribution.

Figure 1: Word lengths cluster between 4 and 12 letters, then tail off.

The histogram shows the skew clearly: a dense cluster of short words between 4 and 12 letters, then a thin tail that extends far to the right. This matters because algorithms that assume a maximum word length will fail on the 2,891 outlier words beyond the interquartile fences. We also confirmed that a tokenizer on the classic pangram has a 9.09 percent out-of-vocabulary rate, driven entirely by "supercalifragilisticexpialidocious", which is a useful reminder that real text always contains surprises.

Technique toolbox

The word list becomes a playground for seven classic algorithm design techniques. Each one gets a minimal implementation and a measured result, and each one teaches a different way to spend a search budget.

Two pointers technique scans a sorted structure with a left and a right index, avoiding nested loops entirely. We intersect two sorted lists of 3,000 words each, first with a naive double loop and then with two indices that advance based on comparisons. The naive version takes 0.07123 seconds and finds 22 common words. The two-pointer version finds the same 22 words in 0.00047 seconds, a 150-fold speedup that comes entirely from removing the inner loop.

def intersection_two_pointer(a, b):
    i = 0
    j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1  # a[i] can't match anything later in b
        else:
            j += 1
    return result

The key insight is that both lists are sorted, so when a[i] is smaller than b[j], we know a[i] cannot appear anywhere later in b. We advance the smaller pointer and never look back.

Sliding windows keep a contiguous range [left, right] and update it incrementally as the window moves. We find the longest substring with all distinct letters, first with a naive double loop and then with a window that grows when characters are new and shrinks when a repeat appears. On a 300-character window drawn from the word list, both methods return 14 as the longest unique substring. The naive version takes 0.00024 seconds. The sliding window takes 0.00006 seconds. The gap widens on longer inputs, because the sliding window touches each character at most twice.

Divide and conquer splits a problem into independent halves, solves each recursively, and combines the results. We compute the longest common prefix of 500 words that all start with "pre". Both the naive sequential method and the divide-and-conquer version return "pre" as the common prefix. The divide-and-conquer version follows the recurrence pattern we classify next.

Master Theorem classifies recurrences of the form T(n) = aT(n/b) + O(n^k). It compares k with log_b a to decide whether the splits or the combine step dominates. For the concrete recurrence T(n) = 2T(n/2) + O(n), the theorem gives the solution class Theta(n log n), which matches the measured call counts of our merge-sort implementation on inputs of size 1,000, 2,000, and 4,000. Our implementation confirms the textbook classes: binary search is Theta(log n), merge sort is Theta(n log n), and the divide-and-conquer LCP is linear in the number of words when word length is bounded.