Problem
GPT-style tokenizers use Byte Pair Encoding: start from single characters and repeatedly merge the most common pair of neighbors into a new symbol.
- Split every word in
wordsinto characters. Repeated words count multiple times. - Count every pair of adjacent symbols across all words.
- Pick the most frequent pair. If pairs tie, pick the one that is smallest when you compare (first symbol, second symbol) as strings.
- Replace every occurrence of that pair, left to right, with the merged symbol, and record the merged symbol.
- Repeat
num_mergestimes, or stop early when no word has two symbols left.
Implement bpe_merges(words, num_merges).
Input
words: The training words (lowercase letters).
num_merges: How many merges to learn.
Output
Return the merged symbols in the order they were learned.
Constraints
1 ≤ number of words ≤ 1,000, 1 ≤ length of each word ≤ 30
0 ≤ num_merges ≤ 200
Examples
Input:
words = ["low", "lower", "lowest"]
num_merges = 2
Expected output:
expected = ["lo", "low"]Input:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;
Expected output:
std::vector<std::string> expected = {"lo", "low"};Input:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;
Expected output:
string[] expected = new string[] {"lo", "low"};Explanation
Pairs: "l o" and "o w" appear 3 times each; the tie goes to "l o" ("l" < "o"), giving "lo". Now "lo w" appears 3 times, giving "low". Result: ["lo", "low"].
Input:
words = ["aaa"]
num_merges = 3
Expected output:
expected = ["aa", "aaa"]Input:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;
Expected output:
std::vector<std::string> expected = {"aa", "aaa"};Input:
string[] words = new string[] {"aaa"};
long num_merges = 3;
Expected output:
string[] expected = new string[] {"aa", "aaa"};Explanation
"aaa" has the pair "a a" twice. Merging left to right gives "aa" + "a". Then "aa a" merges into "aaa", and the word is a single symbol, so the third merge has nothing to do. Result: ["aa", "aaa"].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Track the current symbol sequence for each word and repeatedly count neighboring pairs across all repeated words.
Hint 2
Use pair counting plus deterministic tie-breaking by comparing the pair as two strings, and then update every word left to right.
Hint 3
Watch words that shrink to one symbol; when no adjacent pair exists anywhere, stop even if merges remain.
Expected complexity
O(num_merges * total_symbols) time, O(total_symbols) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.