Longest Unequal Adjacent Groups Subsequence II solution and explanation
9 more videos on this problem
Longest Unequal Adjacent Groups Subsequence II | Leetcode 2901Techdose · 23:35 · 2K views
2901. Longest Unequal Adjacent Groups Subsequence II | 2900 | Leetcode Biweekly 115codingMohan · 27:43 · 1K views
2901. Longest Unequal Adjacent Groups Subsequence II | Leetcode Daily - PythonLeetcode Daily · 12:57 · 692 views
2901. Longest Unequal Adjacent Groups Subsequence II || LIS + Parent 🔥 || Dynamic Programming 🔥Ayush Rao · 12:32 · 621 views
Leetcode 2901 Longest Unequal Adjacent Groups Subsequence II | Biweekly 115 | DP | C++ solutionCoding Samurai's · 19:03 · 548 views
2901. Longest Unequal Adjacent Groups Subsequence II (Leetcode Medium)Programming Live with Larry · 19:12 · 372 views
2901. Longest Unequal Adjacent Groups Subsequence II || Leetcode Daily Challenge || DP || LISEye on AI and DSA · 17:14 · 176 views
LeetCode Longest Unequal Adjacent Groups Subsequence II Solution | 2901 | Code CrackCode Crack · 11:54 · 148 views
Longest Unequal Adjacent Groups Subsequence II | LeetCode 2901 | DP | Java Code | Developer CoderDeveloper Coder · 31:36 · 133 views
2901. Longest Unequal Adjacent Groups Subsequence II | Java | Leetcode |JavAttack · 11:08 · 130 views
The 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 eachjwhere0 < j + 1 < k. words[ij]andwords[ij+1]are equal in length, and the hamming distance between them is1, where0 < 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 is1.
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] <= nwordsconsists of distinct strings.words[i]consists of lowercase English letters.
Approach overview
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.
Solution
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.
class Solution:
def getWordsInLongestSubsequence(
self, 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
n = len(groups)
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]class Solution {
public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
int n = groups.length;
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;
}
}class Solution {
public:
vector<string> getWordsInLongestSubsequence(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;
};
int n = groups.size();
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;
}
};function getWordsInLongestSubsequence(words: string[], groups: number[]): string[] {
const n = groups.length;
const f: number[] = Array(n).fill(1);
const g: number[] = Array(n).fill(-1);
let mx = 1;
const check = (s: string, t: string) => {
if (s.length !== t.length) {
return false;
}
let cnt = 0;
for (let i = 0; i < s.length; ++i) {
if (s[i] !== t[i]) {
++cnt;
}
}
return cnt === 1;
};
for (let i = 0; i < n; ++i) {
for (let 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]);
}
}
}
const ans: string[] = [];
for (let i = 0; i < n; ++i) {
if (f[i] === mx) {
for (let j = i; ~j; j = g[j]) {
ans.push(words[j]);
}
break;
}
}
return ans.reverse();
}func getWordsInLongestSubsequence(words []string, groups []int) []string {
check := func(s, t string) bool {
if len(s) != len(t) {
return false
}
cnt := 0
for i := range s {
if s[i] != t[i] {
cnt++
}
}
return cnt == 1
}
n := len(groups)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1
g[i] = -1
}
mx := 1
for i, x := range groups {
for j, y := range groups[:i] {
if x != y && f[i] < f[j]+1 && check(words[i], words[j]) {
f[i] = f[j] + 1
g[i] = j
if mx < f[i] {
mx = f[i]
}
}
}
}
ans := make([]string, 0, mx)
for i, x := range f {
if x == mx {
for j := i; j >= 0; j = g[j] {
ans = append(ans, words[j])
}
break
}
}
slices.Reverse(ans)
return ans
}impl Solution {
pub fn get_words_in_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
fn check(s: &str, t: &str) -> bool {
s.len() == t.len() && s.chars().zip(t.chars()).filter(|(a, b)| a != b).count() == 1
}
let n = groups.len();
let mut f = vec![1; n];
let mut g = vec![-1; n];
let mut mx = 1;
for i in 0..n {
let x = groups[i] as usize;
for j in 0..i {
let y = groups[j] as usize;
if x != y && f[i] < f[j] + 1 && check(&words[i], &words[j]) {
f[i] = f[j] + 1;
g[i] = j as i32;
mx = mx.max(f[i]);
}
}
}
let mut ans = vec![];
let mut i = n - 1;
while f[i] != mx {
i -= 1;
}
let mut j = i as i32;
while j >= 0 {
ans.push(words[j as usize].clone());
j = g[j as usize];
}
ans.reverse();
ans
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Longest Unequal Adjacent Groups Subsequence II easy or hard?
The problem is rated Medium because the logic combines subsequence dynamic programming with a string constraint. Once the DP transition dp[i] = max(dp[j] + 1) is identified with the group and Hamming checks, the implementation becomes straightforward.
Longest Unequal Adjacent Groups Subsequence II Python/Java solution
Most solutions implement dynamic programming with two arrays: dp for subsequence length and parent for reconstruction. The same logic translates directly across Python, Java, C++, Go, TypeScript, and Rust because the algorithm mainly uses loops and string comparison.
How to solve Longest Unequal Adjacent Groups Subsequence II in O(n)?
An O(n) solution is generally not feasible because the algorithm must compare many pairs of words to verify the one-character difference constraint. Most implementations rely on dynamic programming with pairwise checks, which leads to O(n^2 * L) time complexity.
What is the best approach for Longest Unequal Adjacent Groups Subsequence II?
Dynamic Programming is the most effective approach. Define dp[i] as the longest valid subsequence ending at index i and try extending it from every previous index j where groups differ and the words have Hamming distance exactly 1. This produces an O(n^2 * L) solution where L is the word length.
Is Longest Unequal Adjacent Groups Subsequence II asked at Google/Amazon/Meta?
Problems combining subsequence dynamic programming and string comparison frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this pattern test DP state transitions, string comparison logic, and reconstruction of the optimal sequence.
What data structure is used in Longest Unequal Adjacent Groups Subsequence II?
The core data structures are arrays for dynamic programming and parent tracking. The algorithm iterates through the words array while comparing strings character-by-character to compute Hamming distance.
What is the time complexity of Longest Unequal Adjacent Groups Subsequence II?
The optimal solution runs in O(n^2 * L) time. Each pair of indices (j, i) is checked once, and verifying the Hamming distance between two words takes O(L) time. The space complexity is O(n) for the DP and parent arrays used to reconstruct the subsequence.