Build an Ordered Merge Table

Task

Write build_merge_table(tokens, replacements). It returns a pair (final_tokens, table) and applies the supplied replacement strings one at a time.

At each step, inspect the current token list. If it has fewer than two tokens, stop and ignore the remaining replacements. Otherwise, count every overlapping adjacent pair, where a pair is a two-item tuple of neighboring tokens. Choose the pair with the highest count. If counts tie, choose the pair whose first occurrence has the earliest current start position. If a further tie ever remains, compare the pair tuples in ordinary tuple order.

Replace every non-overlapping occurrence of the chosen pair in one left-to- right pass. A match appends the current replacement string and advances by two tokens; a non-match copies one current token and advances by one. Do not scan or replace a replacement created during that same step. Append (chosen_pair, replacement, count) to table after each completed step.

replacements is a bounded sequence of strings. The token values are strings, and all input sequences must remain unchanged.

Example

The first step counts ('a', 'b') twice and merges both non-overlapping occurrences. The second step sees the newly produced current list, where ('AB', 'AB') occurs once. The replacement "BC" is not rescanned during that second step.

When several pairs have the same count, the earliest current start decides; this makes the result independent of dictionary construction details. For example, the first pair in ["x", "y", "z"] wins the tie between ('x', 'y') and ('y', 'z').

Your implementation

Edit solution.py and keep this function name and signature:

Return a new token list and a new table list. The table records only completed steps, in replacement order. A step counts overlapping pairs, but its replacement scan consumes a matched pair and therefore does not overlap. If the current list becomes shorter than two tokens, do not create more table rows. Do not mutate either input sequence.