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.Problem Overview: You are given two arrays: words and groups. Build the longest subsequence of words such that for every pair of adjacent elements in the subsequence, their corresponding groups values are different. The relative order of elements must remain the same.
Approach 1: Greedy (O(n) time, O(1) extra space)
The constraint only requires that adjacent selected elements have different group IDs. Because there is no restriction on distance between elements, the optimal strategy is to scan from left to right and pick a word whenever its group differs from the last chosen group. Start by selecting the first word, then iterate through the array and compare groups[i] with the group of the last element added to the subsequence. If they differ, append the current word to the result. This works because skipping a valid candidate never helps create a longer subsequence later. The algorithm performs a single pass through the array and stores only the result list, making it linear time and constant auxiliary space. This pattern commonly appears in Greedy problems where a locally optimal decision guarantees the global optimum.
Approach 2: Dynamic Programming (O(n²) time, O(n) space)
A more general solution treats the problem as a subsequence optimization task. Let dp[i] represent the length of the longest valid subsequence ending at index i. For each i, iterate over all previous indices j < i. If groups[i] != groups[j], you can extend the subsequence ending at j, so update dp[i] = max(dp[i], dp[j] + 1). Track the predecessor index to reconstruct the actual sequence of words. This approach resembles classic subsequence DP patterns often used with Array and Dynamic Programming problems. Although correct, it is unnecessary here because the constraint involves only adjacent inequality and does not require comparing distant states.
Recommended for interviews: The greedy approach is what interviewers expect. It demonstrates that you recognized the constraint applies only to consecutive chosen elements and that skipping valid elements cannot improve the result. Mentioning the DP formulation shows you understand the general subsequence framework, but implementing the O(n) greedy scan signals stronger problem‑solving judgment.
The greedy approach involves traversing the groups array and selecting elements that form an alternating pattern. We can iterate through the array, keeping track of the last selected group's value and select the current word if its corresponding group value is different from the last selected value. This approach ensures that we build a valid alternating subsequence as we proceed through each element.
This C code iterates through the array of words and selects words whose corresponding group values alternate. It uses the variable lastGroup to track the group value of the last selected word. Whenever a new word is added to the result, it updates lastGroup with the current group's value. This way, we form a subsequence where consecutive word indexes have differing group values.
Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
Space Complexity: O(n) for storing the result.
This approach involves using Dynamic Programming to construct the longest alternating subsequence. By maintaining a DP table, we can determine the longest subsequence ending at each index, using previously calculated results. This approach efficiently decides when to extend the subsequence ending at a given position.
The above C code uses nested loops to populate a `dp` array, where each element at index i indicates the maximum length of an alternating subsequence that ends at that position. The solution reconstructs this subsequence from the `dp` states, finding the longest sequence possible.
Time Complexity: O(n^2) due to the nested iteration.
Space Complexity: O(n), required for the `dp` array.
We can traverse the array groups, and for the current index i, if i=0 or groups[i] neq groups[i - 1], we add words[i] to the answer array.
The time complexity is O(n), where n is the length of the array groups. The space complexity is O(n).
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the array. We make a single pass through the array. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to the nested iteration. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Scan | O(n) | O(1) | Best for this problem since only adjacent group inequality matters |
| Dynamic Programming | O(n²) | O(n) | Useful when subsequence constraints require comparing many previous states |
Longest Unequal Adjacent Groups Subsequence I | Simple Intuition | Leetcode 2900 | codestorywithMIK • codestorywithMIK • 6,002 views views
Watch 9 more video solutions →Practice Longest Unequal Adjacent Groups Subsequence I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor