OA: Subword tokenizer: train, encode, decode

Build Tokenizer, a class that learns how to cut text into reusable pieces called tokens. At this level it has one method.

• train(text: str, num_merges: int) -> list[str]:

  1. Start with text cut into single characters. Each one is a token.
  2. Count every pair of neighbouring tokens. Every position counts, so overlapping pairs count separately: "aaa" holds the pair ("a", "a") twice.
  3. Pick the pair with the highest count. On a tie, pick the pair whose left token is smallest in plain string order, and if the left tokens are equal, the one whose right token is smallest. If no pair occurs at least twice, stop.
  4. Merge that pair everywhere: scan left to right, and each time its two tokens stand next to each other, replace them with one token (their concatenation) and carry on after it. So "a", "a", "a" becomes "aa", "a".
  5. Repeat steps 2 to 4 until num_merges merges are done, or step 3 stops early.

  Return the new tokens in the order they were learned.

• Each call to train starts from scratch and forgets any earlier training.

tok = Tokenizer()
tok.train("abababcab", 10)   # ["ab", "abab"]
tok.train("hellohello", 2)   # ["el", "ell"]   4-way tie at first: "el" < "he" < "ll" < "lo"
tok.train("aaaa", 5)         # ["aa"]          then "aa", "aa" holds its only pair once
tok.train("banana", 3)       # ["an"]
tok.train("abcd", 3)         # []

Constraints: text is lowercase letters, 0 <= len(text) <= 2000, 0 <= num_merges <= 200. At this size, recounting all pairs after every merge is fine.