Select a longest subsequence of words so that neighboring chosen words always come from different groups.
Problem
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 validj
Return 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.
Input Format
- An integer
n, the number of words. - A list
wordsof lengthn. - A list
groupsof lengthn, where each entry identifies the group of the corresponding word.
Output Format
Return a subsequence of words with maximum possible length such that no two adjacent chosen words have the same group.
Constraints
1 <= n <= $10^{5}$words.length == groups.length == n- Group labels may be integers or strings depending on the platform representation.
- Any valid longest subsequence is acceptable.
Example 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
Unlock deeper context for this problem
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.