# Longest Unequal Adjacent Groups Subsequence I
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-i)
Canonical: https://scaleengineer.com/dsa/problems/longest-unequal-adjacent-groups-subsequence-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, String
**Companies:** [ZS Associates](https://scaleengineer.com/companies/zs-associates), [fourkites](https://scaleengineer.com/companies/fourkites)
---
## Problem
You are given a string array `words` and a **binary** array `groups` both of length `n`.

A subsequence of `words` is **alternating** if for any two _consecutive_ strings in the sequence, their corresponding elements at the _same_ indices in `groups` are **different** (that is, there _cannot_ be consecutive 0 or 1).

Your task is to select the **longest alternating** subsequence from `words`.

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 <= 100`
* `1 <= words[i].length <= 10`
* `groups[i]` is either `0` or `1.`
* `words` consists of **distinct** strings.
* `words[i]` consists of lowercase English letters.

# Approaches
## Dynamic Programming
This approach uses dynamic programming, a standard technique for optimization problems on sequences. It's similar to the classic Longest Increasing Subsequence (LIS) problem. We build a solution by determining the length of the longest alternating subsequence that can be formed ending at each index `i`.
**Time:** O(n^2), where `n` is the number of words. The nested loops used to populate the `dp` array result in a quadratic time complexity. · **Space:** O(n), where `n` is the number of words. We use two arrays, `dp` and `parent`, both of size `n`. The result list also requires up to O(n) space.
**Pros:** It is a robust and general method that correctly solves the problem.; The logic is a standard application of dynamic programming, making it a good general-purpose tool for similar sequence problems.
**Cons:** The O(n^2) time complexity is not optimal for this problem and can be slow for larger values of `n` (though it passes given the constraints).
### Explanation
In this method, we define `dp[i]` as the length of the longest alternating subsequence ending with the word `words[i]`. To calculate `dp[i]`, we must find a preceding index `j < i` such that `groups[j] != groups[i]`, and the subsequence ending at `j` is as long as possible. The recurrence relation is `dp[i] = 1 + max({dp[j] | 0 <= j < i and groups[j] != groups[i]})`. If no such `j` exists, `dp[i]` is simply 1 (the subsequence containing only `words[i]`).

To reconstruct the actual subsequence, we use an additional `parent` array. `parent[i]` stores the index `j` that provided the maximum length for `dp[i]`. After computing the `dp` and `parent` arrays for all indices, we find the index with the maximum `dp` value, which marks the end of a longest subsequence. We then trace back from this end index using the `parent` array to build the result.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<String> getLongestUnequalAdjacentGroupsSubsequence(String[] words, int[] groups) {
        int n = words.length;
        if (n == 0) {
            return new ArrayList<>();
        }

        int[] dp = new int[n];
        int[] parent = new int[n];
        int maxLength = 0;
        int endIndex = -1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            parent[i] = -1;
            for (int j = 0; j < i; j++) {
                if (groups[i] != groups[j]) {
                    if (1 + dp[j] > dp[i]) {
                        dp[i] = 1 + dp[j];
                        parent[i] = j;
                    }
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                endIndex = i;
            }
        }

        List<String> result = new ArrayList<>();
        int curr = endIndex;
        while (curr != -1) {
            result.add(words[curr]);
            curr = parent[curr];
        }
        Collections.reverse(result);

        return result;
    }
}
```
### Algorithm
- Initialize a `dp` array of size `n` with all values set to 1. `dp[i]` will store the length of the longest alternating subsequence ending at index `i`.
- Initialize a `parent` array of size `n` with all values set to -1. `parent[i]` will store the predecessor's index in the longest subsequence ending at `i`.
- Iterate through the `words` array with an outer loop for `i` from 0 to `n-1`.
- Inside, have a nested loop for `j` from 0 to `i-1`.
- If `groups[i]` is different from `groups[j]`, it means `words[i]` can extend the subsequence ending at `words[j]`. Check if `1 + dp[j]` is greater than the current `dp[i]`.
- If it is, update `dp[i] = 1 + dp[j]` and `parent[i] = j`.
- After filling the `dp` array, find the index `endIndex` that has the maximum value in `dp`. This is the last element of a longest subsequence.
- Reconstruct the subsequence by starting from `endIndex` and backtracking using the `parent` array until an index of -1 is reached.
- Reverse the reconstructed list to get the correct order and return it.

## Greedy Single-Pass Approach
A more efficient solution can be achieved with a greedy single-pass approach. The core idea is that the longest alternating subsequence can be formed by simply picking the first word, and then iterating through the rest, adding a word whenever its group differs from the group of the previously considered word. This identifies and picks one word from each contiguous block of same-grouped elements, guaranteeing an alternating and longest subsequence.
**Time:** O(n), where `n` is the number of words. The algorithm involves a single pass through the input arrays. · **Space:** O(L), where `L` is the length of the longest subsequence. In the worst case, `L=n` (e.g., for `groups = [0,1,0,1,...]`), so the space is O(n) to store the result. Excluding the output, the space is O(1).
**Pros:** Highly efficient, with a linear time complexity of O(n).; Very simple to understand and implement.; Requires minimal extra space, aside from the storage for the output list.
**Cons:** The simplicity of this greedy approach is tied to the binary nature of the `groups` array. It might not be directly applicable to more complex variations of the problem with more than two groups or different adjacency rules.
### Explanation
The problem requires a subsequence where adjacent elements have different group values. The `groups` array, being binary, can be viewed as a sequence of contiguous blocks of 0s and 1s (e.g., `[0,0,1,1,1,0]`). An alternating subsequence can, at most, pick one element from each of these blocks. Thus, the maximum possible length of such a subsequence is the total number of blocks.

A simple and effective greedy strategy is to pick the first element of each block. This can be implemented by first adding `words[0]` to our result. Then, we iterate from `i = 1` to `n-1` and add `words[i]` to our result if and only if `groups[i]` is different from `groups[i-1]`. A change from the previous group value signifies the beginning of a new block, so we select its first element. This method constructs a valid alternating subsequence of maximum length in a single pass.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> getLongestUnequalAdjacentGroupsSubsequence(String[] words, int[] groups) {
        List<String> result = new ArrayList<>();
        if (words.length == 0) {
            return result;
        }

        // Always include the first word
        result.add(words[0]);

        // Iterate from the second word
        for (int i = 1; i < words.length; i++) {
            // Add the current word if its group is different from the previous one
            if (groups[i] != groups[i - 1]) {
                result.add(words[i]);
            }
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty list called `result`.
- If the input `words` array is empty, return the empty list.
- Add the first word, `words[0]`, to the `result` list, as any longest subsequence must start with some element, and starting with the first is a valid greedy choice.
- Iterate through the arrays from the second element, i.e., for `i` from 1 to `n-1`.
- For each element, compare its group `groups[i]` with the group of the immediately preceding element `groups[i-1]`.
- If `groups[i] != groups[i-1]`, it indicates the start of a new group block. Add the word `words[i]` to the `result` list.
- After the loop completes, return the `result` list.

# Solutions
### Java

```java
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]) {
        ans.add(words[i]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]]

```