Sign Shop Letter Blocks
A sign shop builds shop-front lettering from pre-cut wooden blocks. Besides single letters, it keeps blocks for common letter groups like th, ing and bake, because one block is quicker to mount than four. The rule on the workbench: reading left to right, always grab the longest block that fits the next letters exactly. If no group fits, use a single letter.
Language models read text the same way. Before a model sees anything, a tokenizer cuts the text into pieces from a fixed vocabulary, and some tokenizers use this same longest-match-first rule. That is why a common word is often one token while a rare word breaks into several.
Your task
Write tokenize(text, pieces). Start at the first letter. At each position, find the longest string in pieces that appears in text starting exactly at that position. Add it to the result and move past it. If no piece matches, add the single letter at that position and move one step.
Return the list of tokens in order. Joined together they must spell text. An empty text gives an empty list.
tokenize(text: string, pieces: string[]) → string[]
Examples
text = "bakery" pieces = ["ba", "bake", "ry", "er", "y"]
["bake", "ry"]
At position 0 both "ba" and "bake" fit; take the longer, "bake". At position 4, "ry" fits ("er" does not start there). The text is used up: ["bake", "ry"].
text = "thinking" pieces = ["th", "in", "ink", "ing", "king"]
["th", "ink", "ing"]
"th" at 0. At 2, "in" and "ink" fit, take "ink". At 5, "ing" fits. Result ["th", "ink", "ing"]. Notice greedy does not look ahead: it never considers "in" + "king", even though that would also work.
text = "zoo" pieces = ["oo", "bake"]
["z", "oo"]
No piece starts with "z", so it becomes a single-letter token. Then "oo" fits. Result ["z", "oo"].
Constraints
- 0 ≤ text.length ≤ 10,000
- 0 ≤ pieces.length ≤ 1,000
- 1 ≤ pieces[i].length ≤ 20
- text and pieces use lowercase letters a to z only. pieces may contain repeats.
Start with brute force
At every position, loop over all the pieces and check whether each one starts there, keeping the longest. With 10,000 letters and 1,000 pieces of up to 20 letters, that is up to 200 million character comparisons.
Most of that work is wasted: at any position only about 20 lengths are possible, and a set can say whether a given chunk is a piece in roughly one step. So check those few lengths instead of every piece.
Hints
0 of 4 shown- Hint 1
In the first example, both "ba" and "bake" fit at position 0. If you scanned the pieces in the order given and took the first that fits, which would you pick?
- Hint 2
The rule asks for the longest match, so the order of
piecesmust not matter. One option: check every piece at every position and keep the longest that fits. How many checks is that for a long text and a big vocabulary? - Hint 3
Flip the question around. Instead of asking every piece "do you fit here?", ask the text: "is the next 4-letter chunk a piece? The next 3? The next 2?" A set answers each question in one step.
- Hint 4
Put the pieces in a set and note the longest piece length
L. At positioni, try lengths frommin(L, remaining)down to 2, and take the first substring that is in the set. If none is, take one letter. Advanceiby the length you took.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The greedy rule means you never undo a choice: at each position you take the longest piece that fits and move on. So the only real question is how to find that longest piece quickly.
Trace "bakery" with pieces ["ba", "bake", "ry", "er", "y"]. The set holds those five strings and the longest has 4 letters.
- i = 0: try "bake" (4 letters). In the set. Token "bake", i = 4.
- i = 4: only 2 letters left, so try "ry". In the set. Token "ry", i = 6.
- i = 6 is the end. Result ["bake", "ry"].
Greedy is fast and predictable, but not always the fewest tokens: with pieces ab, abc, cd, the text "abcd" becomes "abc" + "d", not "ab" + "cd". Real tokenizers accept that trade-off. A trie of the pieces would avoid re-reading letters, but with pieces this short the set is simpler.
function tokenize(text, pieces) {
const vocab = new Set(pieces);
let longest = 0;
for (const p of pieces) longest = Math.max(longest, p.length);
const tokens = [];
let i = 0;
while (i < text.length) {
let len = Math.min(longest, text.length - i);
// Try the longest possible piece first, then shorter ones.
while (len > 1 && !vocab.has(text.slice(i, i + len))) len--;
len = Math.max(len, 1); // a single letter is always allowed
tokens.push(text.slice(i, i + len));
i += len;
}
return tokens;
}def tokenize(text, pieces):
vocab = set(pieces)
longest = max((len(p) for p in pieces), default=1)
tokens = []
i = 0
while i < len(text):
length = min(longest, len(text) - i)
# Try the longest possible piece first, then shorter ones.
while length > 1 and text[i:i + length] not in vocab:
length -= 1
length = max(length, 1) # a single letter is always allowed
tokens.append(text[i:i + length])
i += length
return tokensRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.