words and an array colors of the same length: colors[i] is the color of the card that carries words[i].
Build a relay: pick some cards while keeping their order in the array (any card may be skipped) so that every two neighbouring picked cards:
- have different colors;
- carry words of the same length that differ in exactly one position.
Return the words of the longest relay in order. If several longest relays exist, choose like this: the last card has the smallest possible index; then, moving from the end towards the start, each earlier card also has the smallest possible index (as long as the relay stays the longest).
A relay of a single card is always allowed.words=['cold', 'cord', 'card', 'ward', 'word'], colors=[1, 2, 1, 2, 2] → ['cold', 'cord', 'card', 'ward']
The chain cold → cord → card → ward works: neighbours differ in exactly one letter and their colors alternate. word cannot follow ward because they share a color.
words=['map', 'mop', 'top'], colors=[3, 3, 1] → ['mop', 'top']
map and mop share a color, and map and top differ in two letters. The longest chain is mop → top.
words=['sun', 'moon', 'soon'], colors=[1, 2, 3] → ['moon', 'soon']
moon → soon has length 2, and no other chain of that length exists, so the answer is unique.
n = len(words) = len(colors) ≤ 1000len(words[i]) ≤ 10, lowercase English letters onlycolors[i] ≤ nwords=['cold', 'cord', 'card', 'ward', 'word'], colors=[1, 2, 1, 2, 2]
['cold', 'cord', 'card', 'ward']
Run checks the first 3 tests in your browser. Submit checks all 251 tests on the server, hidden ones included.