You are given a string array words and a binary array groups both of length n, where words[i] is associated with groups[i].
Your task is to select the longest alternating subsequence from words. A subsequence of words is alternating if for any two consecutive strings in the sequence, their corresponding elements in the binary array groups differ. Essentially, you are to choose strings such that adjacent elements have non-matching corresponding bits in the groups array.
Formally, you need to find the longest subsequence of an array of indices [0, 1, ..., n - 1] denoted as [i0, i1, ..., ik-1], such that groups[ij] != groups[ij+1] for each 0 <= j < k - 1 and then find the words corresponding to these indices.
Return the selected subsequence. If there are multiple answers, return any of them.
Note: The elements in words are distinct.
Example 1:
Input: words = ["e","a","b"], groups = [0,0,1]
Output: ["e","b"]
Explanation: A subsequence that can be selected is ["e","b"] because groups[0] != groups[2]. Another subsequence that can be selected is ["a","b"] because groups[1] != groups[2]. It can be demonstrated that the length of the longest subsequence of indices that satisfies the condition is 2.
Example 2:
Input: words = ["a","b","c","d"], groups = [1,0,1,1]
Output: ["a","b","c"]
Explanation: A subsequence that can be selected is ["a","b","c"] because groups[0] != groups[1] and groups[1] != groups[2]. Another subsequence that can be selected is ["a","b","d"] because groups[0] != groups[1] and groups[1] != groups[3]. It can be shown that the length of the longest subsequence of indices that satisfies the condition is 3.
Constraints:
1 <= n == words.length == groups.length <= 1001 <= words[i].length <= 10groups[i] is either 0 or 1.words consists of distinct strings.words[i] consists of lowercase English letters.In #2900 Longest Unequal Adjacent Groups Subsequence I, you are given arrays representing words and their corresponding group IDs. The goal is to build the longest subsequence of words such that the group value of adjacent elements is different. Since the order of elements must remain the same, this becomes a subsequence selection problem.
A key observation is that only the last chosen group matters when deciding whether the next word can be added. A greedy approach works well: iterate through the array and include a word whenever its group differs from the group of the previously chosen word. This naturally builds the longest valid subsequence while preserving order.
Alternatively, the problem can also be reasoned about using a simple dynamic programming perspective, where each position tracks the longest valid subsequence ending there with alternating groups.
The greedy strategy runs in O(n) time and requires minimal extra space, making it the most efficient and practical solution for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Traversal | O(n) | O(1) |
| Dynamic Programming | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
This problem can be solved greedily.
Begin by constructing the answer starting with the first number in <code>groups</code>.
For each index <code>i</code> in the range <code>[1, n - 1]</code>, add <code>i</code> to the answer if <code>groups[i] != groups[i - 1]</code>.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving subsequences, greedy choices, and simple dynamic programming are common in technical interviews. While this exact problem may vary, the underlying pattern of alternating constraints appears frequently.
The optimal approach is a greedy traversal. Iterate through the words and include an element in the subsequence whenever its group differs from the previously selected group's value. This ensures the longest valid subsequence while maintaining the original order.
The constraint only depends on the group of the previously chosen element. If the current group differs, selecting it can never reduce the optimal subsequence length, which makes the greedy choice safe and optimal.
Basic arrays or lists are sufficient. Since the algorithm only needs to track the last selected group and append valid words, no advanced data structures are required.