You are given an integer n, an array of strings words, and an array of integers groups, both of length n.

The Hamming distance between two strings of equal length is defined as the number of positions at which the corresponding characters are different.

You need to select the longest subsequence of indices $[i_0, i_1, \dots, i_{k - 1}]$ from the range $[0, n - 1]$ such that for all $0 \leq j < k - 1$:

• groups$[i_j] \neq$ groups$[i_{j + 1}]$

• words$[i_j]$.length $=$ words$[i_{j + 1}]$.length

• The Hamming distance between words$[i_j]$ and words$[i_{j + 1}]$ is equal to $1$.

Return an array of strings containing the elements of words corresponding to the chosen sequence of indices. If there are multiple valid subsequences of the maximum length, you may return any of them.

Note: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Constraints:

• $1 \leq n ==$ words.length $==$ groups.length $\leq 1000$

• $1 \leq$ words[i].length $\leq 10$

• $1 \leq$ groups[i] $\leq n$

• words consists of distinct strings.

• words[i] consists of lowercase English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.