# Longest Unequal Adjacent Groups Subsequence II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii)
Canonical: https://scaleengineer.com/dsa/problems/longest-unequal-adjacent-groups-subsequence-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String
**Companies:** [fourkites](https://scaleengineer.com/companies/fourkites)
---
## Problem
You are given a string array `words`, and an array `groups`, both arrays having length `n`.

The **hamming distance** between two strings of equal length is the number of positions at which the corresponding characters are **different**.

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`, the following holds:

* For **adjacent** indices in the subsequence, their corresponding groups are **unequal**, i.e., `groups[ij] != groups[ij+1]`, for each `j` where `0 < j + 1 < k`.
* `words[ij]` and `words[ij+1]` are **equal** in length, and the **hamming distance** between them is `1`, where `0 < j + 1 < k`, for all indices in the subsequence.

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_.

**Note:** strings in `words` may be **unequal** in length.

**Example 1:**

**Input:** words = \["bab","dab","cab"\], groups = \[1,2,2\]

**Output:** \["bab","cab"\]

**Explanation:** A subsequence that can be selected is `[0,2]`.

* `groups[0] != groups[2]`
* `words[0].length == words[2].length`, and the hamming distance between them is 1.

So, a valid answer is `[words[0],words[2]] = ["bab","cab"]`.

Another subsequence that can be selected is `[0,1]`.

* `groups[0] != groups[1]`
* `words[0].length == words[1].length`, and the hamming distance between them is `1`.

So, another valid answer is `[words[0],words[1]] = ["bab","dab"]`.

It can be shown that the length of the longest subsequence of indices that satisfies the conditions is `2`.

**Example 2:**

**Input:** words = \["a","b","c","d"\], groups = \[1,2,3,4\]

**Output:** \["a","b","c","d"\]

**Explanation:** We can select the subsequence `[0,1,2,3]`.

It satisfies both conditions.

Hence, the answer is `[words[0],words[1],words[2],words[3]] = ["a","b","c","d"]`.

It has the longest length among all subsequences of indices that satisfy the conditions.

Hence, it is the only answer.

**Constraints:**

* `1 <= n == words.length == groups.length <= 1000`
* `1 <= words[i].length <= 10`
* `1 <= groups[i] <= n`
* `words` consists of **distinct** strings.
* `words[i]` consists of lowercase English letters.

# Approaches
## Brute-Force Dynamic Programming
This approach uses dynamic programming to solve the problem. It treats the problem as finding the longest path in a Directed Acyclic Graph (DAG), where each word's index is a node. A directed edge exists from index `j` to `i` (with `j < i`) if `words[i]` can validly follow `words[j]`. The solution iterates through all possible pairs of indices `(j, i)` where `j < i` to build up the lengths of subsequences ending at each index.
**Time:** O(n^2 * L), where `n` is the number of words and `L` is the maximum length of a word. The two nested loops give a factor of O(n^2), and the Hamming distance calculation inside the loop takes O(L) time. · **Space:** O(n), where `n` is the number of words. This is for the `dp` and `parent` arrays.
**Pros:** The logic is straightforward and directly follows the definition of the problem.; It correctly solves the problem by exhaustively checking all valid predecessor-successor relationships.
**Cons:** The time complexity of O(n^2 * L) can be too slow if `n` is very large, although it passes within the given constraints.
### Explanation
We define `dp[i]` as the length of the longest valid subsequence ending at index `i`. To reconstruct the subsequence later, we also use a `parent[i]` array to store the index of the predecessor of `i` in the longest subsequence found for it.

The algorithm proceeds as follows:
1.  Initialize `dp` array of size `n` with all elements as `1`, because any single word forms a valid subsequence of length 1.
2.  Initialize `parent` array of size `n` with all elements as `-1`.
3.  We iterate with `i` from `0` to `n-1`. For each `i`, we iterate with `j` from `0` to `i-1` to check all possible predecessors.
4.  Inside the inner loop, we check if `words[i]` can follow `words[j]`. This is true if their groups are different, their lengths are equal, and their Hamming distance is 1.
5.  If they are compatible and we can form a longer subsequence by appending `words[i]` to the subsequence ending at `words[j]` (i.e., `1 + dp[j] > dp[i]`), we update `dp[i]` and set `parent[i] = j`.
6.  After iterating through all `j` for a given `i`, `dp[i]` holds the maximum length of a subsequence ending at `i`. We keep track of the overall maximum length and the index where it ends.
7.  Finally, we reconstruct the subsequence by backtracking from the end index using the `parent` array, collect the corresponding words, and reverse them to get the correct order.

```java
import java.util.*;

class Solution {
    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);

        int maxLength = 1;
        int endIndex = 0;

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

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

    private boolean isCompatible(String w1, String w2, int g1, int g2) {
        if (g1 == g2 || w1.length() != w2.length()) {
            return false;
        }
        int diff = 0;
        for (int k = 0; k < w1.length(); k++) {
            if (w1.charAt(k) != w2.charAt(k)) {
                diff++;
            }
            if (diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
}
```
### Algorithm
- Initialize a `dp` array of size `n` with all values set to `1`. `dp[i]` will store the length of the longest valid subsequence ending at index `i`.
- Initialize a `parent` array of size `n` with all values set to `-1`. `parent[i]` will store the predecessor of index `i` in its longest subsequence.
- Initialize `maxLength = 1` and `endIndex = 0` to track the end of the overall longest subsequence found so far.
- Iterate through the words with an outer loop from `i = 0` to `n-1`.
- Inside, have a nested loop from `j = 0` to `i-1`.
- For each pair `(j, i)`, check if `words[i]` can follow `words[j]` in a valid subsequence. This requires three conditions:
  1. `groups[j] != groups[i]`
  2. `words[j].length() == words[i].length()`
  3. The Hamming distance between `words[j]` and `words[i]` is exactly 1.
- If the conditions are met and `dp[j] + 1 > dp[i]`, update `dp[i] = dp[j] + 1` and `parent[i] = j`.
- After the inner loop for `i` finishes, if `dp[i]` is greater than `maxLength`, update `maxLength` and `endIndex`.
- After the loops complete, reconstruct the longest subsequence by starting from `endIndex` and backtracking using the `parent` array until `-1` is reached.
- Reverse the collected indices to get the correct order and return the corresponding words.

## Optimized Dynamic Programming with Hashing
This approach enhances the dynamic programming solution by optimizing the search for a valid predecessor. Instead of a nested loop that checks all previous indices, for each word `words[i]`, we generate all its potential 'neighbor' words (those with a Hamming distance of 1). We then use a hash map to instantly check if any of these neighbors have been encountered before. This avoids the O(n) inner loop, leading to a more efficient solution.
**Time:** O(n * L^2), where `n` is the number of words and `L` is their max length. For each of the `n` words, we generate O(L * 25) neighbors. Generating a neighbor string and looking it up in the hash map both take O(L) time. Thus, the total time is O(n * L * L) = O(n * L^2). · **Space:** O(n * L), where `n` is the number of words and `L` is their max length. The `wordToIndex` map can store up to `n` words, contributing O(n * L) to the space. The `dp` and `parent` arrays take O(n) space.
**Pros:** Much more efficient than the brute-force DP, especially when `n` is large and `L` is small.; Avoids the O(n^2) complexity by replacing the inner loop with hash map lookups, which are much faster.
**Cons:** Requires more space for the hash map, which could be significant if words are long (though not an issue with the given constraints).; The implementation is slightly more complex due to the logic for generating neighbor words and managing the hash map.
### Explanation
The core DP state `dp[i]` and `parent[i]` array remain the same as the brute-force approach. The key improvement is in how we find the best predecessor for `words[i]`.

1.  We maintain a hash map, `wordToIndex`, which maps a word string to its index in the input array.
2.  As we iterate from `i = 0` to `n-1`, for the current `word = words[i]`, we don't look at all `j < i`. Instead, we generate all possible strings that could be valid predecessors. These are strings of the same length as `words[i]` with a Hamming distance of 1.
3.  We can generate these 'neighbor' strings by iterating through each character position of `words[i]` and substituting the character with every other letter of the alphabet.
4.  For each generated `neighborWord`, we perform a quick lookup in `wordToIndex`. If it exists, we get its index `j`. Since we process indices sequentially, we are guaranteed that `j < i`.
5.  We then check the group condition (`groups[j] != groups[i]`). If it holds, we have found a valid predecessor `j` and can potentially update `dp[i]` and `parent[i]` if it leads to a longer subsequence.
6.  After processing all neighbors for `words[i]`, we add `words[i]` and its index `i` to the `wordToIndex` map, making it available for subsequent words in the iteration.
7.  The final steps of finding the maximum length and reconstructing the path are identical to the previous approach.

```java
import java.util.*;

class Solution {
    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);
        
        Map<String, Integer> wordToIndex = new HashMap<>();
        int maxLength = 1;
        int endIndex = 0;

        for (int i = 0; i < n; i++) {
            String currentWord = words[i];
            int currentGroup = groups[i];
            int len = currentWord.length();

            char[] chars = currentWord.toCharArray();
            for (int k = 0; k < len; k++) {
                char originalChar = chars[k];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == originalChar) continue;
                    
                    chars[k] = c;
                    String neighbor = new String(chars);
                    
                    if (wordToIndex.containsKey(neighbor)) {
                        int j = wordToIndex.get(neighbor);
                        if (groups[j] != currentGroup) {
                            if (dp[j] + 1 > dp[i]) {
                                dp[i] = dp[j] + 1;
                                parent[i] = j;
                            }
                        }
                    }
                }
                chars[k] = originalChar; // Backtrack for the next position
            }
            
            wordToIndex.put(currentWord, i);

            if (dp[i] > maxLength) {
                maxLength = dp[i];
                endIndex = i;
            }
        }
        
        List<String> result = new ArrayList<>();
        int currentIndex = endIndex;
        while (currentIndex != -1) {
            result.add(words[currentIndex]);
            currentIndex = parent[currentIndex];
        }
        Collections.reverse(result);
        return result;
    }
}
```
### Algorithm
- Initialize `dp[n]` with `1`s and `parent[n]` with `-1`s.
- Initialize an empty `HashMap<String, Integer>` named `wordToIndex` to store words and their first-seen indices.
- Initialize `maxLength = 1` and `endIndex = 0`.
- Iterate `i` from `0` to `n-1`:
  - Let `currentWord = words[i]`.
  - Generate all potential predecessor words ('neighbors') for `currentWord`. A neighbor is a string of the same length with a Hamming distance of 1. This is done by changing one character at a time.
  - For each `neighbor`:
    - Check if the `neighbor` exists in `wordToIndex`. If so, retrieve its index `j`.
    - If `groups[j]` is not equal to `groups[i]` and `dp[j] + 1 > dp[i]`, update `dp[i] = dp[j] + 1` and `parent[i] = j`.
  - After checking all neighbors, add `currentWord` and its index `i` to `wordToIndex`.
  - Update `maxLength` and `endIndex` if `dp[i]` is the new maximum.
- Reconstruct the result by backtracking from `endIndex` using the `parent` array, then reverse it.

# Solutions
### Java

```java
class Solution {
public
  List<String> getWordsInLongestSubsequence(int n, String[] words,
                                            int[] groups) {
    int[] f = new int[n];
    int[] g = new int[n];
    Arrays.fill(f, 1);
    Arrays.fill(g, -1);
    int mx = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (groups[i] != groups[j] && f[i] < f[j] + 1 &&
            check(words[i], words[j])) {
          f[i] = f[j] + 1;
          g[i] = j;
          mx = Math.max(mx, f[i]);
        }
      }
    }
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      if (f[i] == mx) {
        for (int j = i; j >= 0; j = g[j]) {
          ans.add(words[j]);
        }
        break;
      }
    }
    Collections.reverse(ans);
    return ans;
  }
private
  boolean check(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) != t.charAt(i)) {
        ++cnt;
      }
    }
    return cnt == 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> getWordsInLongestSubsequence(int n, vector<string> &words,
                                              vector<int> &groups) {
    auto check = [](string &s, string &t) {
      if (s.size() != t.size()) {
        return false;
      }
      int cnt = 0;
      for (int i = 0; i < s.size(); ++i) {
        cnt += s[i] != t[i];
      }
      return cnt == 1;
    };
    vector<int> f(n, 1);
    vector<int> g(n, -1);
    int mx = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (groups[i] != groups[j] && f[i] < f[j] + 1 &&
            check(words[i], words[j])) {
          f[i] = f[j] + 1;
          g[i] = j;
          mx = max(mx, f[i]);
        }
      }
    }
    vector<string> ans;
    for (int i = 0; i < n; ++i) {
      if (f[i] == mx) {
        for (int j = i; ~j; j = g[j]) {
          ans.emplace_back(words[j]);
        }
        break;
      }
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]: def check(s: str, t: str) -> bool: return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1 f = [1] * n g = [- 1] * n mx = 1 for i, x in enumerate(groups): for j, y in enumerate(groups[: i]): if x != y and f[i] < f[j] + 1 and check(words[i], words[j]): f[i] = f[j] + 1 g[i] = j mx = max(mx, f[i]) ans = [] for i in range(n): if f[i] == mx: j = i while j >= 0: ans . append(words[j]) j = g[j] break return ans[:: - 1]

```