Watch 10 video solutions for Longest Unequal Adjacent Groups Subsequence II, a medium level problem involving Array, String, Dynamic Programming. This walkthrough by codestorywithMIK has 10,498 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |