Extra Characters in a String: Dynamic Programming over a Trie of Words

Problem

You have a string s and a list of distinct dictionary words. Cut s into non-overlapping pieces so that as many characters as possible belong to pieces that are dictionary words; any characters that are not covered by a word are “extra”. Words can be reused. Return the minimum number of extra characters. This is LeetCode 2707, Extra Characters in a String. Strings are short (tens of characters) and lowercase.

Examples

s = "datalake",  words = ["data", "lake", "la"]     ->  0   ("data" + "lake")
s = "xdatay",    words = ["data"]                   ->  2   (x and y are extra)
s = "abc",       words = ["d"]                      ->  3
s = "aaa",       words = ["a"]                      ->  0

Approach 1: brute force (recursion over every split)

At each position, either treat the current character as extra or jump past any dictionary word that starts here. Try all choices.

def min_extra_brute(s, words):
    vocab = set(words)

    def solve(i):
        if i == len(s):
            return 0
        best = 1 + solve(i + 1)
        for j in range(i + 1, len(s) + 1):
            if s[i:j] in vocab:
                best = min(best, solve(j))
        return best

    return solve(0)

Complexity: exponential in the worst case, because the same suffix is solved again and again.

Approach 2: optimal (suffix DP with a trie)

Only the starting position matters for the rest of the answer, so store one number per position. Compute from the end backwards: dp[i] = 1 + dp[i + 1] if you drop s[i], or dp[j + 1] for every word s[i..j]. To find those words without slicing, walk a trie from s[i] character by character; every node marked as a word end gives a candidate j, and the walk stops when the trie has no child for the next character.

def build_trie(words):
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = True
    return root

def min_extra(s, words):
    root = build_trie(words)
    n = len(s)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        dp[i] = 1 + dp[i + 1]
        node = root
        for j in range(i, n):
            node = node.get(s[j])
            if node is None:
                break
            if "$" in node:
                dp[i] = min(dp[i], dp[j + 1])
    return dp[0]

Why it is correct: any optimal split of the suffix at i starts with either an extra s[i] or a word s[i..j], and the rest is an optimal split of a shorter suffix, which dp already holds. The trie walk lists exactly the words that start at i.

Complexity: O(n²) time for the DP (each start walks at most n characters) plus O(total word length) to build the trie; O(n + total word length) space.

Tests

import random

for f in (min_extra, min_extra_brute):
    assert f("datalake", ["data", "lake", "la"]) == 0
    assert f("xdatay", ["data"]) == 2
    assert f("abc", ["d"]) == 3
    assert f("aaa", ["a"]) == 0
    assert f("", ["a"]) == 0
    assert f("abc", []) == 3
    assert f("abcab", ["abc", "ab", "cab"]) == 0   # several splits possible
    assert f("abcab", ["abca", "bcab", "a"]) == 0  # longest-first greedy gives 1

random.seed(5)
for _ in range(300):
    s = "".join(random.choice("ab") for _ in range(random.randint(0, 10)))
    words = list({"".join(random.choice("ab") for _ in range(random.randint(1, 3)))
                  for _ in range(random.randint(0, 4))})
    assert min_extra(s, words) == min_extra_brute(s, words)
print("ok")

Edge cases and pitfalls

• Do not stop at the first word that matches. The shorter word may leave a worse remainder than a longer one (and the reverse), so take the minimum over all of them.
• A greedy “longest match first” split is wrong: on "abcab" with words ["abca", "bcab", "a"] it takes "abca" and leaves b extra, while "a" + "bcab" leaves nothing.
• Break out of the trie walk as soon as a character has no child; that is where the speed-up comes from.
• Reusing words is allowed, so the trie never needs to track usage.

Where this shows up in data engineering

Segmenting text against a dictionary appears when parsing concatenated identifiers, splitting hashtags or URL slugs into words, or tokenising product codes made of known parts. The trie-plus-DP pattern is also how longest-match tokenisers and some log parsers find known prefixes quickly, and the “cost of leftovers” framing is a handy way to score how well a record matches a reference vocabulary.