Select a longest subsequence of words so that neighboring chosen words always come from different groups.
You are given a list of words and a parallel list of group labels, where groups[i] is the group of words[i].
Choose a subsequence of indices i1 < i2 < ... < ik such that for every adjacent pair in the subsequence, the corresponding group labels are different:
groups[ij] != groups[ij+1] for all valid jReturn any longest valid subsequence of words.
A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.
Because this is the I version, the goal is to return one maximum-length valid subsequence, not necessarily all of them.
n, the number of words.words of length n.groups of length n, where each entry identifies the group of the corresponding word.Return a subsequence of words with maximum possible length such that no two adjacent chosen words have the same group.
1 <= n <= $10^{5}$words.length == groups.length == nExample 1
Input
words = ["a", "b", "c", "d", "e"], groups = [1, 1, 2, 2, 1]
Output
["a", "c", "e"]
Explanation
Choose indices 0, 2, and 4. Their groups are 1, 2, and 1, so every adjacent pair differs.
Example 2
Input
words = ["hello", "world", "leetcode"], groups = [3, 3, 3]
Output
["hello"]
Explanation
Any two chosen words would have the same group, so the longest valid subsequence has length 1.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.