EF-T11: Minimum dictionary tokenization

Exercise contract#

Given an ASCII text and a dictionary of nonempty ASCII tokens, return the minimum number of dictionary tokens whose concatenation equals the entire text, or -1 when no such concatenation exists. Dictionary duplicates are ignored. The empty text needs zero tokens. Reject an empty token or non-ASCII text/token.

Constraints

• 0 <= text.length <= 5,000 ASCII bytes.
• 0 <= dictionary.length <= 1,000 and every accepted token has 1 to 100 ASCII bytes.
• The sum of distinct token lengths is at most 50,000 bytes.
• Tokens may be reused any number of times and matching is case-sensitive.

Examples

text="abc", dictionary=["a","ab","bc"]

2The complete construction is a + bc.

text="", dictionary=["a"]

0No token is needed to construct the empty prefix.

Derive the approach#

Baseline: Enumerate every sequence of tokens and stop a branch when it no longer matches the next text bytes. Repeated suffixes create an exponential search tree.

1. Let dp[i] be the minimum tokens needed to construct text[0:i], with dp[0]=0 and every other state initially unreachable.
2. For each reachable boundary i, try every distinct token. If it matches starting at i, relax dp[i+len(token)] with dp[i]+1.
3. Every transition advances to a longer prefix, so left-to-right evaluation respects dependencies and terminates.
4. The final state answers the whole text. If it remains unreachable, return -1 rather than a fabricated partial count.

Time

O(n · d · L) worst case

Space

O(n + D) for DP and distinct-token storage

Assumptions

n is ASCII text length, d is the number of distinct tokens, L is maximum token length, D is total distinct-token storage, and prefix comparison examines at most L bytes.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def minimum_tokens(text, dictionary):
    if any(ord(character) > 127 for character in text) or any(not token or any(ord(character) > 127 for character in token) for token in dictionary):
        raise ValueError("text and nonempty tokens must be ASCII")
    tokens = list(dict.fromkeys(dictionary))
    unreachable = len(text) + 1
    dp = [unreachable] * (len(text) + 1)
    dp[0] = 0
    for index in range(len(text)):
        if dp[index] == unreachable:
            continue
        for token in tokens:
            if text.startswith(token, index):
                end = index + len(token)
                dp[end] = min(dp[end], dp[index] + 1)
    return -1 if dp[-1] == unreachable else dp[-1]

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;

static int minimumTokens(String text, List<String> dictionary) {
    if (!isAscii(text)) throw new IllegalArgumentException("text must be ASCII");
    LinkedHashSet<String> tokens = new LinkedHashSet<>();
    for (String token : dictionary) {
        if (token == null || token.isEmpty() || !isAscii(token)) throw new IllegalArgumentException("tokens must be nonempty ASCII");
        tokens.add(token);
    }
    int unreachable = text.length() + 1;
    int[] dp = new int[text.length() + 1];
    Arrays.fill(dp, unreachable);
    dp[0] = 0;
    for (int index = 0; index < text.length(); index++) {
        if (dp[index] == unreachable) continue;
        for (String token : tokens) {
            if (text.startsWith(token, index)) {
                int end = index + token.length();
                dp[end] = Math.min(dp[end], dp[index] + 1);
            }
        }
    }
    return dp[text.length()] == unreachable ? -1 : dp[text.length()];
}

static boolean isAscii(String value) {
    if (value == null) return false;
    for (int index = 0; index < value.length(); index++) if (value.charAt(index) > 127) return false;
    return true;
}

Deterministic test plan#

Transfer and follow-ups#

• Return one minimum-token construction with a deterministic dictionary-order tie rule.
• Group tokens by first byte and reassess the complexity bound.

Write what dp[i] means before translating the token matches into transitions.

Authorship and review#

Original exercise wording and cases using a standard one-dimensional dynamic-programming idea; no employer provenance or uniqueness claim is made.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09