Skip to main content
Talentd

Longest Unequal Adjacent Groups Subsequence II - Solution & Explanation

MediumArrayStringDynamic Programming12 min readAsked at: Meta, Fourkites
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking / Brute ForceO(2^n * L)O(n)Only useful for conceptual understanding or very small inputs
Dynamic Programming with Parent TrackingO(n^2 * L)O(n)General case; standard interview solution that reconstructs the subsequence
DP with Early Length FilteringO(n^2 * L)O(n)Same DP approach but skips Hamming checks when word lengths differ, improving practical performance

Video Solution

Longest Unequal Adjacent Groups Subsequence II | Leetcode 2901 • Techdose • 2,581 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Longest Unequal Adjacent Groups Subsequence II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays