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:
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 <= 10001 <= words[i].length <= 101 <= groups[i] <= nwords consists of distinct strings.words[i] consists of lowercase English letters.Problem Overview: You are given two arrays: words and groups. The task is to build the longest subsequence of indices such that adjacent elements come from different groups and their corresponding words differ by exactly one character (Hamming distance = 1). The subsequence must preserve the original order, and the result returns the sequence of words.
Approach 1: Backtracking / Brute Force (Exponential Time)
The most direct approach is to try every possible subsequence and validate whether it satisfies the constraints. For each candidate subsequence, check two conditions for adjacent elements: group IDs must differ and the two words must have the same length with exactly one character mismatch. This requires computing Hamming distance for each adjacent pair. The time complexity grows exponentially because every element can either be included or skipped, resulting in roughly O(2^n * L) time and O(n) recursion space. This approach only works for very small inputs but helps clarify the constraints.
Approach 2: Dynamic Programming with Reconstruction (O(n^2 * L))
The practical solution uses dynamic programming. Let dp[i] represent the length of the longest valid subsequence ending at index i. For each index i, iterate through all previous indices j < i. If groups[i] != groups[j] and the words have the same length with Hamming distance exactly 1, then i can extend the subsequence ending at j. Update using dp[i] = max(dp[i], dp[j] + 1). Checking Hamming distance takes O(L), where L is the word length. Since each pair (j, i) is examined once, the total time complexity is O(n^2 * L) with O(n) extra space.
To reconstruct the actual subsequence, maintain a parent array storing the previous index used to reach i. After filling the DP table, locate the index with the largest dp value and backtrack using the parent pointers to build the answer in reverse order.
This solution relies heavily on pairwise comparisons across the array, making it a natural mix of array iteration and string comparison logic. Pre-checking word length before computing Hamming distance avoids unnecessary character comparisons and keeps the implementation efficient.
Recommended for interviews: The dynamic programming approach is what interviewers expect. Brute force demonstrates understanding of the constraints but is not scalable. Implementing dp[i] transitions with Hamming distance checks and reconstructing the subsequence shows strong problem-solving skills and familiarity with classic subsequence DP patterns.
We define f[i] as the length of the longest adjacent non-equal subsequence ending with the i-th word, and g[i] as the predecessor index of the longest adjacent non-equal subsequence ending with the i-th word. Initially, we set f[i] = 1 and g[i] = -1.
In addition, we define a variable mx to represent the length of the longest adjacent non-equal subsequence.
We traverse i and j \in [0, i), and if groups[i] neq groups[j], f[i] \lt f[j] + 1, and the Hamming distance between words[i] and words[j] is 1, we update f[i] = f[j] + 1, g[i] = j, and update mx = max(mx, f[i]).
Finally, we find the index i corresponding to the maximum value in the f array, and then continuously search backwards from i until we find g[i] = -1, which gives us the longest adjacent non-equal subsequence.
The time complexity is O(n^2 times L), and the space complexity is O(n). Here, L represents the maximum length of a word.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / Brute Force | O(2^n * L) | O(n) | Only useful for conceptual understanding or very small inputs |
| Dynamic Programming with Parent Tracking | O(n^2 * L) | O(n) | General case; standard interview solution that reconstructs the subsequence |
| DP with Early Length Filtering | O(n^2 * L) | O(n) | Same DP approach but skips Hamming checks when word lengths differ, improving practical performance |
Longest Unequal Adjacent Groups Subsequence II | Why Greedy Fails | Leetcode 2901 | codestorywithMIK • codestorywithMIK • 10,498 views views
Watch 9 more video solutions →Practice Longest Unequal Adjacent Groups Subsequence II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor