Longest Unequal Adjacent Groups Subsequence I solution and explanation
9 more videos on this problem
Longest Unequal Adjacent Groups Subsequence I | Simple Intuition | Leetcode 2900 | codestorywithMIKcodestorywithMIK · 15:09 · 6K views
2900. Longest Unequal Adjacent Groups Subsequence I || GreedyAyush Rao · 5:57 · 844 views
2900. Longest Unequal Adjacent Groups Subsequence I (Leetcode Medium)Programming Live with Larry · 13:02 · 306 views
Longest Unequal Adjacent Groups Subsequence I | Leetcode 2900 | Approach + Code with explanation.Pirai's Academy · 8:04 · 288 views
Leetcode 2900. Longest Unequal Adjacent Groups Subsequence I | Leetcode 2900 Python SolutionStatLearn Tech · 11:31 · 265 views
2900. Longest Unequal Adjacent Groups Subsequence I | Leetcode Daily - PythonLeetcode Daily · 6:30 · 241 views
Longest Unequal Adjacent Groups Subsequence I - Leetcode 2900 - PythonTim Huang · 2:55 · 225 views
2900. Longest Unequal Adjacent Groups Subsequence IRounaq Khandelwal · 7:08 · 207 views
Leetcode-2900 || Longest Unequal Adjacent Groups Subsequence I || Optimal SolutionTurbo My Tech · 8:30 · 139 views
Longest Unequal Adjacent Groups Subsequence I - LeetCode 2900ThinkOutsideTheBox · 14:06 · 59 views
The problem
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 either0or1.wordsconsists of distinct strings.words[i]consists of lowercase English letters.
Approach overview
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.
Approach 1: Greedy Approach
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.
def longest_alternating_subsequence(words, groups):
result = []
last_group = -1
for i in range(len(words)):
if groups[i] != last_group:
result.append(words[i])
last_group = groups[i]
return result
words = ["e", "a", "b"]
groups = [0, 0, 1]
result = longest_alternating_subsequence(words, groups)
print(result)import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<String> longestAlternatingSubsequence(String[] words, int[] groups) {
List<String> result = new ArrayList<>();
int lastGroup = -1;
for (int i = 0; i < words.length; i++) {
if (groups[i] != lastGroup) {
result.add(words[i]);
lastGroup = groups[i];
}
}
return result;
}
public static void main(String[] args) {
String[] words = {"e", "a", "b"};
int[] groups = {0, 0, 1};
List<String> result = longestAlternatingSubsequence(words, groups);
for (String word : result) {
System.out.print(word + " ");
}
}
}#include <iostream>
#include <vector>
#include <string>
std::vector<std::string> longestAlternatingSubsequence(const std::vector<std::string>& words, const std::vector<int>& groups) {
std::vector<std::string> result;
int lastGroup = -1;
for (size_t i = 0; i < words.size(); ++i) {
if (groups[i] != lastGroup) {
result.push_back(words[i]);
lastGroup = groups[i];
}
}
return result;
}
int main() {
std::vector<std::string> words = {"e", "a", "b"};
std::vector<int> groups = {0, 0, 1};
auto result = longestAlternatingSubsequence(words, groups);
for (const auto& word : result)
std::cout << word << " ";
return 0;
}function longestAlternatingSubsequence(words, groups) {
const result = [];
let lastGroup = -1;
for (let i = 0; i < words.length; i++) {
if (groups[i] !== lastGroup) {
result.push(words[i]);
lastGroup = groups[i];
}
}
return result;
}
const words = ["e", "a", "b"];
const groups = [0, 0, 1];
console.log(longestAlternatingSubsequence(words, groups));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void longestAlternatingSubsequence(char** words, int* groups, int n, char** result, int* resultSize) {
int lastGroup = -1;
*resultSize = 0;
for (int i = 0; i < n; i++) {
if (groups[i] != lastGroup) {
result[*resultSize] = words[i];
(*resultSize)++;
lastGroup = groups[i];
}
}
}
int main() {
char* words[] = {"e", "a", "b"};
int groups[] = {0, 0, 1};
int n = 3;
char* result[n];
int resultSize;
longestAlternatingSubsequence(words, groups, n, result, &resultSize);
for (int i = 0; i < resultSize; i++) {
printf("%s ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static List<string> LongestAlternatingSubsequence(string[] words, int[] groups) {
List<string> result = new List<string>();
int lastGroup = -1;
for (int i = 0; i < words.Length; i++) {
if (groups[i] != lastGroup) {
result.Add(words[i]);
lastGroup = groups[i];
}
}
return result;
}
static void Main() {
string[] words = { "e", "a", "b" };
int[] groups = { 0, 0, 1 };
var result = LongestAlternatingSubsequence(words, groups);
foreach (var word in result)
Console.Write(word + " ");
}
}This Python function implements the greedy strategy by keeping track of the last chosen group's value, adding a new word to the result list when the current group is different from the last. It guarantees selecting an alternating sequence efficiently.
Time Complexity: O(n).
Space Complexity: O(n) to store the resulting subsequence.
Approach 2: Dynamic Programming Approach
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.
def longest_alternating_subsequence(words, groups):
dp = [1] * len(words)
max_length = 1
end_index = 0
for i in range(1, len(words)):
for j in range(i):
if groups[i] != groups[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
if dp[i] > max_length:
max_length = dp[i]
end_index = i
result = []
while max_length > 0:
if dp[end_index] == max_length:
result.append(words[end_index])
max_length -= 1
end_index -= 1
return result[::-1]
words = ["e", "a", "b"]
groups = [0, 0, 1]
result = longest_alternating_subsequence(words, groups)
print(result)import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<String> longestAlternatingSubsequence(String[] words, int[] groups) {
int[] dp = new int[words.length];
int maxLength = 1, endIndex = 0;
for (int i = 0; i < words.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (groups[i] != groups[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
endIndex = i;
}
}
List<String> result = new ArrayList<>(maxLength);
for (int i = endIndex, index = maxLength - 1; i >= 0; i--) {
if (dp[i] == maxLength) {
result.add(0, words[i]);
maxLength--;
}
}
return result;
}
public static void main(String[] args) {
String[] words = {"e", "a", "b"};
int[] groups = {0, 0, 1};
List<String> result = longestAlternatingSubsequence(words, groups);
for (String word : result) {
System.out.print(word + " ");
}
}
}#include <iostream>
#include <vector>
#include <string>
std::vector<std::string> longestAlternatingSubsequence(const std::vector<std::string>& words, const std::vector<int>& groups) {
std::vector<int> dp(words.size(), 1);
int maxLength = 1;
int endIndex = 0;
for (size_t i = 1; i < words.size(); ++i) {
for (size_t j = 0; j < i; ++j) {
if (groups[i] != groups[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
endIndex = i;
}
}
std::vector<std::string> result(maxLength);
for (int i = endIndex, index = maxLength - 1; i >= 0; --i) {
if (dp[i] == maxLength) {
result[index--] = words[i];
--maxLength;
}
}
return result;
}
int main() {
std::vector<std::string> words = {"e", "a", "b"};
std::vector<int> groups = {0, 0, 1};
auto result = longestAlternatingSubsequence(words, groups);
for (const auto& word : result)
std::cout << word << " ";
return 0;
}function longestAlternatingSubsequence(words, groups) {
let dp = Array(words.length).fill(1);
let maxLength = 1;
let endIndex = 0;
for (let i = 1; i < words.length; i++) {
for (let j = 0; j < i; j++) {
if (groups[i] !== groups[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
endIndex = i;
}
}
const result = [];
while (maxLength > 0) {
if (dp[endIndex] === maxLength) {
result.push(words[endIndex]);
maxLength--;
}
endIndex--;
}
return result.reverse();
}
const words = ["e", "a", "b"];
const groups = [0, 0, 1];
console.log(longestAlternatingSubsequence(words, groups));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
void longestAlternatingSubsequence(char** words, int* groups, int n, char** result, int* resultSize) {
int dp[n];
int maxLength = 0;
int endIndex = 0;
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (groups[i] != groups[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
endIndex = i;
}
}
*resultSize = maxLength;
int index = maxLength - 1;
for (int i = endIndex; i >= 0; --i) {
if (dp[i] == maxLength) {
result[index--] = words[i];
maxLength--;
}
}
}
int main() {
char* words[] = {"e", "a", "b"};
int groups[] = {0, 0, 1};
int n = 3;
char* result[n];
int resultSize;
longestAlternatingSubsequence(words, groups, n, result, &resultSize);
for (int i = 0; i < resultSize; i++) {
printf("%s ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static List<string> LongestAlternatingSubsequence(string[] words, int[] groups) {
int n = words.Length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = 1;
int maxLength = 1, endIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (groups[i] != groups[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
endIndex = i;
}
}
List<string> result = new List<string>();
while (maxLength > 0) {
if (dp[endIndex] == maxLength) {
result.Insert(0, words[endIndex]);
maxLength--;
}
endIndex--;
}
return result;
}
static void Main() {
string[] words = { "e", "a", "b" };
int[] groups = { 0, 0, 1 };
var result = LongestAlternatingSubsequence(words, groups);
foreach (var word in result) Console.Write(word + " ");
}
}Python employs a dynamic programming method, initializing a `dp` list to retain the longest sequence length at each position. The solution navigates through all possible previous states to construct and later backtrack the sequence.
Time Complexity: O(n^2).
Space Complexity: O(n) for the `dp` list.
Approach 3: Greedy
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).
function getLongestSubsequence(words: string[], groups: number[]): string[] {
const ans: string[] = [];
for (let i = 0; i < groups.length; ++i) {
if (i === 0 || groups[i] !== groups[i - 1]) {
ans.push(words[i]);
}
}
return ans;
}func getLongestSubsequence(words []string, groups []int) (ans []string) {
for i, x := range groups {
if i == 0 || x != groups[i-1] {
ans = append(ans, words[i])
}
}
return
}impl Solution {
pub fn get_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
let mut ans = Vec::new();
for (i, &g) in groups.iter().enumerate() {
if i == 0 || g != groups[i - 1] {
ans.push(words[i].clone());
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n). |
| Dynamic Programming Approach | Time Complexity: O(n^2). |
| Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Longest Unequal Adjacent Groups Subsequence I easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate around 67%. The key observation is that only adjacent elements in the chosen subsequence must differ in group value, which allows a straightforward greedy solution.
Longest Unequal Adjacent Groups Subsequence I Python/Java solution
The greedy algorithm translates directly into Python, Java, C++, C#, and JavaScript. Iterate through the words array, compare adjacent group values, and append valid words to a result list. The implementation remains O(n) across all languages.
How to solve Longest Unequal Adjacent Groups Subsequence I in O(n)?
Iterate through the arrays once while tracking the group of the last selected element. Add the current word to the result only when groups[i] differs from the previously chosen group. This single-pass greedy strategy ensures the subsequence remains valid and maximizes its length.
What is the best approach for Longest Unequal Adjacent Groups Subsequence I?
The optimal approach is a greedy scan. Start with the first word and keep adding words whose group value differs from the last selected group's value. Because the constraint only applies to adjacent elements in the subsequence, this simple rule guarantees the longest valid subsequence in O(n) time.
Is Longest Unequal Adjacent Groups Subsequence I asked at Google/Amazon/Meta?
Problems involving greedy subsequence selection and simple dynamic programming frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem is from LeetCode, the pattern of enforcing constraints between adjacent selections is common in real interview questions.
What data structure is used in Longest Unequal Adjacent Groups Subsequence I?
The solution primarily uses arrays or lists to iterate through the input and store the resulting subsequence. No complex data structures are required for the greedy solution, though the dynamic programming variant uses a DP array to track subsequence lengths.
What is the time complexity of Longest Unequal Adjacent Groups Subsequence I?
The optimal greedy solution runs in O(n) time and O(1) extra space, where n is the number of words. A dynamic programming formulation exists with O(n²) time and O(n) space, but it is unnecessary for this specific constraint.