# 2900. Longest Unequal Adjacent Groups Subsequence I

## Description

You are given an integer n, a 0-indexed string array words, and a 0-indexed binary array groups, both arrays having length n.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i0, i1, ..., ik - 1] having length k, groups[ij] != groups[ij + 1], for each j where 0 < j + 1 < k.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

A subsequence of an array is a new array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Note: strings in words may be unequal in length.

Example 1:

Input: n = 3, words = ["e","a","b"], groups = [0,0,1]
Output: ["e","b"]
Explanation: A subsequence that can be selected is [0,2] because groups[0] != groups[2].
So, a valid answer is [words[0],words[2]] = ["e","b"].
Another subsequence that can be selected is [1,2] because groups[1] != groups[2].
This results in [words[1],words[2]] = ["a","b"].
It is also a valid answer.
It can be shown that the length of the longest subsequence of indices that satisfies the condition is 2.

Example 2:

Input: n = 4, words = ["a","b","c","d"], groups = [1,0,1,1]
Output: ["a","b","c"]
Explanation: A subsequence that can be selected is [0,1,2] because groups[0] != groups[1] and groups[1] != groups[2].
So, a valid answer is [words[0],words[1],words[2]] = ["a","b","c"].
Another subsequence that can be selected is [0,1,3] because groups[0] != groups[1] and groups[1] != groups[3].
This results in [words[0],words[1],words[3]] = ["a","b","d"].
It is also a valid answer.
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 <= 100
• 1 <= words[i].length <= 10
• 0 <= groups[i] < 2
• words consists of distinct strings.
• words[i] consists of lowercase English letters.

## Solutions

Solution 1: 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)$.

• class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
List<String> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (i == 0 || groups[i] != groups[i - 1]) {
}
}
return ans;
}
}

• class Solution {
public:
vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
vector<string> ans;
for (int i = 0; i < n; ++i) {
if (i == 0 || groups[i] != groups[i - 1]) {
ans.emplace_back(words[i]);
}
}
return ans;
}
};

• class Solution:
def getWordsInLongestSubsequence(
self, n: int, words: List[str], groups: List[int]
) -> List[str]:
return [words[i] for i, x in enumerate(groups) if i == 0 or x != groups[i - 1]]

• func getWordsInLongestSubsequence(n int, words []string, groups []int) (ans []string) {
for i, x := range groups {
if i == 0 || x != groups[i-1] {
ans = append(ans, words[i])
}
}
return
}

• function getWordsInLongestSubsequence(n: number, words: string[], groups: number[]): string[] {
const ans: string[] = [];
for (let i = 0; i < n; ++i) {
if (i === 0 || groups[i] !== groups[i - 1]) {
ans.push(words[i]);
}
}
return ans;
}

• impl Solution {
pub fn get_words_in_longest_subsequence(
n: i32,
words: Vec<String>,
groups: Vec<i32>
) -> Vec<String> {
let mut ans = vec![];

for i in 0..n {
if i == 0 || groups[i as usize] != groups[(i - 1) as usize] {
ans.push(words[i as usize].clone());
}
}

ans
}
}