Count Adjacent Symbol Pairs for BPE
Problem statement
You are given a training vocabulary for a byte-pair encoding (BPE) tokenizer: words[i] appears freqs[i] times in the corpus.
Each word is split into symbols: its letters in order, followed by the end-of-word marker "</w>". For example, "low" becomes l, o, w, </w>, with the neighboring pairs (l, o), (o, w) and (w, </w>).
The count of a pair is the total, over all words, of how many times the pair appears in the word times the word's frequency. If the same word appears more than once in words, each entry counts.
Examples
Example 1
words = ["low","lower","newest","widest"]freqs = [5,2,6,3]return = ["e s 9","s t 9","t </w> 9","w e 8","l o 7","o w 7","e w 6","n e 6","w </w> 5","d e 3","i d 3","w i 3","e r 2","r </w> 2"]The classic BPE example. low (5) and lower (2) both contain (l, o) and (o, w), giving 7 each. newest (6) and widest (3) both end in e, s, t, </w>, so (e, s), (s, t) and (t, </w>) get 9 each.
The three pairs with 9 come first, ordered by their left symbols e < s < t. Then (w, e) has 2 + 6 = 8, from lower and newest.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.