Knitting Pattern Shorthand
A knitting club writes patterns as long lists of stitches: k for knit, p for purl, yo for yarn over. Patterns repeat the same neighbours again and again, so the club invents shorthand. They find the pair of neighbouring stitches that appears most often, give it a single new symbol (k then p becomes kp), rewrite the pattern, and repeat.
This is byte pair encoding, the method many language models use to build their token vocabulary. Start from single characters, merge the most common neighbouring pair, repeat thousands of times, and common chunks of words become single tokens.
Your task
Write shorthand(stitches, merges). Repeat the following at most merges times:
- Count every pair of neighbouring tokens
(tokens[i], tokens[i+1])for everyi. Overlapping pairs count separately, so[a, a, a]has the pair(a, a)twice. - Pick the pair with the highest count. If several tie, pick the one whose first occurrence is furthest left. If no pair appears at least twice, stop.
- Scan left to right. Wherever that pair appears, replace the two tokens with one token, their concatenation. A token already used in a merge cannot be part of another merge in the same scan.
Return the final list of tokens.
shorthand(stitches: string[], merges: int) → string[]
Examples
stitches = ["k", "p", "k", "p", "yo", "k", "p"] merges = 1
["kp", "kp", "yo", "kp"]
Pair counts: (k, p) 3, (p, k) 1, (p, yo) 1, (yo, k) 1. Merge (k, p) everywhere: ["kp", "kp", "yo", "kp"].
stitches = ["k", "p", "k", "p", "yo", "k", "p"] merges = 3
["kp", "kp", "yo", "kp"]
After the first merge: [kp, kp, yo, kp]. Now (kp, kp), (kp, yo) and (yo, kp) each appear once. No pair appears twice, so stop early, even though 3 merges were allowed.
stitches = ["k", "k", "k", "p", "k", "k"] merges = 2
["kk", "k", "p", "kk"]
(k, k) appears 3 times (positions 0, 1 and 4). Scanning left to right merges positions 0 and 1, then position 2 is a lone k, then p, then the last two k's merge: [kk, k, p, kk]. Second round: every pair appears once, so stop.
Constraints
- 0 ≤ stitches.length ≤ 2,000
- 0 ≤ merges ≤ 100
- Each token is 1 to 10 lowercase letters.
Start with brute force
For each neighbouring pair, scan the whole list to count how often it appears, and keep the best. That is O(n²) per round. With 2,000 tokens and 100 rounds, that is up to 400 million comparisons.
A hash map counts every pair in a single O(n) pass. Real tokenizer training goes further and only updates the counts that a merge changes, because it runs tens of thousands of rounds on huge text.
Hints
0 of 4 shown- Hint 1
In the third example,
(k, k)is counted 3 times but only 2 merges actually happen. Why can't all three happen? - Hint 2
Counting and merging are separate passes. Counting looks at every neighbouring position. Merging walks left to right and, after a merge, skips past both tokens it used.
- Hint 3
Counting pairs by scanning the list once per distinct pair is slow. Which structure lets you count every pair in one pass? If it remembers insertion order, the first-occurrence tie-break comes almost for free.
- Hint 4
Each round: one pass building a map from pair to count (in first-seen order). Take the first pair with the highest count; stop if that count is below 2. Then one pass building a new list: if the current and next token form the pair, push their concatenation and jump 2, else push the token and move 1. Key the map by the pair, not by the joined string, so
(a, ab)and(aa, b)stay different.
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
Each round is two linear passes: count every neighbouring pair with a hash map, then rebuild the list with the winning pair merged. Most of the difficulty is in following the rules exactly.
Trace [k, k, k, p, k, k] with 2 merges:
- Count: (k, k) appears at positions 0, 1 and 4, so 3 times. (k, p) and (p, k) appear once each. Best is (k, k).
- Merge: i = 0, tokens 0 and 1 match, push "kk", jump to 2. i = 2: "k" then "p", no match, push "k". i = 3: push "p". i = 4: match, push "kk". Result [kk, k, p, kk].
- Count again: (kk, k), (k, p), (p, kk), each once. Nothing appears twice, so stop.
Two easy slips: counting with a key like a + b merges different pairs together (a + ab and aa + b both spell aab), and forgetting to recount after each merge, since a merge creates new pairs and destroys old ones.
function shorthand(stitches, merges) {
let tokens = stitches.slice();
for (let m = 0; m < merges; m++) {
// Count adjacent pairs. A Map keeps keys in first-seen order.
const counts = new Map();
for (let i = 0; i + 1 < tokens.length; i++) {
const key = tokens[i] + ' ' + tokens[i + 1]; // space keeps pairs apart
counts.set(key, (counts.get(key) || 0) + 1);
}
let bestKey = null, bestCount = 1;
for (const [key, c] of counts) if (c > bestCount) { bestKey = key; bestCount = c; }
if (bestKey === null) break; // no pair appears twice
const [a, b] = bestKey.split(' ');
// Replace left to right; a merged pair cannot be reused.
const next = [];
for (let i = 0; i < tokens.length; i++) {
if (i + 1 < tokens.length && tokens[i] === a && tokens[i + 1] === b) {
next.push(a + b);
i++;
} else next.push(tokens[i]);
}
tokens = next;
}
return tokens;
}def shorthand(stitches, merges):
tokens = list(stitches)
for _ in range(merges):
# Count adjacent pairs. A dict keeps keys in first-seen order.
counts = {}
for pair in zip(tokens, tokens[1:]):
counts[pair] = counts.get(pair, 0) + 1
best, best_count = None, 1
for pair, c in counts.items():
if c > best_count:
best, best_count = pair, c
if best is None:
break # no pair appears twice
a, b = best
# Replace left to right; a merged pair cannot be reused.
merged = []
i = 0
while i < len(tokens):
if i + 1 < len(tokens) and tokens[i] == a and tokens[i + 1] == b:
merged.append(a + b)
i += 2
else:
merged.append(tokens[i])
i += 1
tokens = merged
return tokensRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.