Longest Unequal Adjacent Groups Subsequence II

main.md

Question

Approach

I modeled the problem as a directed graph, where each valid pair (i, j) (with i < j) creates an edge if:

• groups[i] != groups[j],
• words[i] and words[j] have equal length,
• and their Hamming distance is 1.

Then I used DP to compute the longest path in this graph. For each node, I store the length of the longest subsequence ending at that node and track its predecessor to later reconstruct the path.

Implementation

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        
        def hamming(a: str, b: str) -> int:
            return sum(c1 != c2 for c1, c2 in zip(a, b))

        dp = [1] * n
        parent = [-1] * n

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

        max_len = max(dp)
        idx = dp.index(max_len)

        path = []
        while idx != -1:
            path.append(words[idx])
            idx = parent[idx]

        return path[::-1] 

Complexities

• Time: O(n² * m)
• Space: O(n)