LeetCode 2901 - Longest Unequal Adjacent Groups Subsequence II

The problem asks us to select the longest subsequence of words from a given array such that adjacent words in the subsequence satisfy two conditions: first, their corresponding groups values are different, and second, the words are of the same length and differ by exactly one…

leetcodemediumarraystringdynamic-programming

LeetCode Problem 2901

Difficulty: 🟡 Medium
Topics: Array, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to select the longest subsequence of words from a given array such that adjacent words in the subsequence satisfy two conditions: first, their corresponding groups values are different, and second, the words are of the same length and differ by exactly one character (hamming distance = 1).

In other words, we are tasked with finding a chain of words where each consecutive word changes exactly one character, and each word comes from a different group. The input arrays words and groups are aligned by index, so words[i] belongs to groups[i]. The output is the actual sequence of words, not just the indices.

Constraints give important limits:

  • 1 <= n <= 1000, which allows algorithms roughly up to O(n^2) without being too slow.
  • 1 <= words[i].length <= 10, so checking hamming distance between two words is cheap.
  • words contains distinct strings, meaning no duplicates need handling.

Important edge cases include:

  • All words have different lengths. Only words of the same length can be compared.
  • Multiple words may satisfy the subsequence conditions; any valid longest subsequence is acceptable.
  • The maximum subsequence could include all words if all conditions are satisfied.

Approaches

Brute Force

A brute force approach would try all subsequences of indices and check if each candidate satisfies the group and hamming distance rules. While correct, this is exponential in n (O(2^n)), which is infeasible for n = 1000. The hamming distance checks themselves are cheap (O(L) for word length L), but the sheer number of subsequences makes brute force impractical.

Optimal Approach

The problem can be transformed into a dynamic programming problem similar to finding the longest path in a DAG:

  1. Construct a graph where each word is a node.
  2. Add a directed edge from word i to word j if groups[i] != groups[j], lengths match, and hamming distance is 1.
  3. Compute the longest path starting from each node using DP.

Since n is small, we can store a DP array dp[i] representing the length of the longest subsequence starting from word i and a parent[i] array to reconstruct the path.

The key insight is that we can precompute all valid transitions using pairwise checks of words with the same length and different groups, then perform DP over this graph.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Enumerate all subsequences and check conditions
Optimal O(n^2 * L) O(n) Build edges between valid word pairs (L ≤ 10), DP to find longest subsequence

Algorithm Walkthrough

  1. Initialize n as the length of words.
  2. Create a DP array dp of length n, initialized to 1, representing the longest subsequence ending at each word.
  3. Create a parent array of length n, initialized to -1, to reconstruct the subsequence.
  4. For each pair of indices i and j where i < j, check:
  • Words have the same length.
  • Words differ by exactly one character (hamming distance = 1).
  • groups[i] != groups[j].

If all conditions hold, consider dp[j] = max(dp[j], dp[i] + 1) and set parent[j] = i if dp[j] increases. 5. After filling DP, find the index end with the maximum dp[end]. 6. Reconstruct the subsequence by tracing back parent[end] until -1. 7. Reverse the reconstructed path and return the corresponding words.

Why it works: Each dp[i] stores the length of the longest valid subsequence ending at i. By only connecting valid transitions (unequal groups, length match, hamming distance 1), we guarantee the subsequence rules are maintained. Backtracking from the maximum dp value yields the correct longest subsequence.

Python Solution

from typing import List

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        dp = [1] * n
        parent = [-1] * n

        def hamming_distance_one(w1: str, w2: str) -> bool:
            if len(w1) != len(w2):
                return False
            diff = sum(a != b for a, b in zip(w1, w2))
            return diff == 1

        for i in range(n):
            for j in range(i + 1, n):
                if groups[i] != groups[j] and hamming_distance_one(words[i], words[j]):
                    if dp[i] + 1 > dp[j]:
                        dp[j] = dp[i] + 1
                        parent[j] = i

        # Find the end index of the longest subsequence
        end = max(range(n), key=lambda x: dp[x])
        result = []
        while end != -1:
            result.append(words[end])
            end = parent[end]
        result.reverse()
        return result

The solution defines a helper function for hamming distance and iterates through all pairs of words to update the DP and parent arrays. Finally, it reconstructs the path efficiently.

Go Solution

func getWordsInLongestSubsequence(words []string, groups []int) []string {
    n := len(words)
    dp := make([]int, n)
    parent := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = 1
        parent[i] = -1
    }

    hammingDistanceOne := func(w1, w2 string) bool {
        if len(w1) != len(w2) {
            return false
        }
        diff := 0
        for i := 0; i < len(w1); i++ {
            if w1[i] != w2[i] {
                diff++
            }
        }
        return diff == 1
    }

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if groups[i] != groups[j] && hammingDistanceOne(words[i], words[j]) {
                if dp[i]+1 > dp[j] {
                    dp[j] = dp[i] + 1
                    parent[j] = i
                }
            }
        }
    }

    end := 0
    for i := 1; i < n; i++ {
        if dp[i] > dp[end] {
            end = i
        }
    }

    result := []string{}
    for end != -1 {
        result = append(result, words[end])
        end = parent[end]
    }

    // Reverse result
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }

    return result
}

Go implementation mirrors Python, using slices and integer arrays. Reversing the slice is done manually. Edge cases with single-word sequences are naturally handled.

Worked Examples

Example 1

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

  • Initialize dp = [1,1,1], parent = [-1,-1,-1]

  • Compare pairs:

  • i=0, j=1: groups differ, hamming distance = 1 → dp[1]=2, parent[1]=0

  • i=0, j=2: groups differ, hamming distance = 1 → dp[2]=2, parent[2]=0

  • i=1, j=2: groups same → skip

  • Max dp = 2 at index 1 or 2 → subsequence could be ["bab","dab"] or ["bab","cab"]

Example 2

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

  • All lengths 1, all groups differ, hamming distance 1 for each pair → dp increments sequentially → dp = [1,2,3,4]
  • Max dp = 4 at index 3 → subsequence ["a","b","c","d"]

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 * L) For each pair of words, we check hamming distance (O(L))
Space O(n) DP and parent arrays of size n

Since L <= 10 and n <= 1000, the solution is efficient.

Test Cases

# Provided examples
assert Solution().getWordsInLongestSubsequence(["bab","dab","cab"], [1,2,2]) in [["bab","dab"], ["bab","cab"]]
assert Solution().getWordsInLongestSubsequence(["a","b","c","d"], [1,2,3,4]) == ["a","b","c","d"]

# Edge cases
assert Solution().getWords