Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A valid next word must come from a different group, have the same length, and differ in exactly one character. These conditions depend only on the previous selected word, so the best subsequence ending at each index contains all the information needed for later extensions.

Approach

Initialize dp[j] to the singleton sequence containing words[j]. For every earlier index i, check the group labels, word lengths, and Hamming distance. Stop comparing characters once more than one mismatch is found.

If the pair is compatible and extending dp[i] produces a longer sequence, replace dp[j] with a copy of dp[i] followed by words[j]. Track the longest sequence across all ending indices. Every valid nonsingleton subsequence has some previous index considered by this transition, so taking the longest extension covers every possibility. The implementation stores complete subsequences rather than predecessor pointers; its copying cost is included in the complexity analysis.

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

        for x in words:
            dp.append([x])

        def hamming(a, b):
            n = len(a)
            count = 0

            for i in range(n):
                if a[i] != b[i]:
                    count += 1
                if count > 1:
                    break

            return count == 1

        mx = 1
        res = [words[0]]

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

        return res

Complexity analysis

Let n be the number of words and L their maximum length. Time: O(n^2 * (L + n)) because pair checks cost O(L) and stored subsequences are copied on improvements. Auxiliary space: O(n^2) for the copied DP subsequences, plus O(n) returned output.