You are given a string array words of length n and a binary integer array groups of the same length n.

A subsequence of words of length $k$ selected at indices $i_0 < i_1 < \dots < i_{k-1}$ is valid if no two adjacent elements in the subsequence share the same group value, meaning groups[$i_j$] != groups[$i_{j+1}$] for all $0 \leq j < k - 1$.

Return an array of strings representing the longest valid subsequence of words. If there are multiple valid subsequences of the maximum length, return any of them.

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

Constraints:

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

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

• groups[i] is either $0$ or $1$

• 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.