Two conveyor belts carry coloured beads, one letter per bead: belt a and belt b, read front to back. You thread every bead from both belts onto one necklace string. At each step you take the front bead of either belt, so each belt's beads keep their own order, but you choose how the two belts interleave.
A colour change is a pair of neighbouring beads on the finished string with different colours. Implement fewest_changes(a: str, b: str) -> int: the smallest number of colour changes you can end up with.
fewest_changes("aab", "abb") # 1 "aaabbb": take a, a, then a from b, then b, b, b
fewest_changes("rgr", "grg") # 3 e.g. "rggrrg" (r from a, g g, r r, g)
If both belts together hold at most one bead, the answer is 0.
Constraints: 0 <= len(a), len(b) <= 300, lowercase letters. The number of interleavings explodes (about 10^178 at full size), so you can't try them all.
Show hint
describe a partly threaded string by how many beads you've taken from each belt and which belt the last bead came from. That tells you the last colour, which is all you need to price the next bead.