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 lo

getWordsInLongestSubsequence.js

/**
 * Finds the longest subsequence of words where each word is 
 * "compatible" with the next and belongs to different groups.
 *
 * @param {string[]} words - Array of words.
 * @param {number[]} groups - Corresponding group identifiers.
 * @return {string[]} - Longest subsequence satisfying the constraints.
 */
var getWordsInLongestSubsequence = function(words, groups) {
    
    const isCompatible = function(word1, word2) {
        if (word1.length !== word2.length) {
            return false; // Words must be of the same length
        }
        
        let differences = 0;
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i]) {
                differences++;
                if (differences > 1) {
                    return false; // More than one character differs
                }
            }
        }
        return true; // Words are compatible
    };

    const n = words.length;
    const dp = Array(n).fill(1); // dp[i] stores length of longest subsequence starting at i
    const prev = Array(n).fill(-1); // prev[i] tracks previous index in longest subsequence

    let maxLen = 0;
    let startIdx = 0;

    // Iterate from the last word to the first
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            // If words are compatible and belong to different groups, update dp
            if (isCompatible(words[i], words[j]) && groups[i] !== groups[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }

        // Track the maximum subsequence length and starting index
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            startIdx = i;
        }
    }

    // Construct the longest subsequence by following prev indices
    const result = [];
    while (startIdx !== -1) {
        result.push(words[startIdx]);
        startIdx = prev[startIdx];
    }

    return result;
};