Longest Unequal Adjacent Groups Subsequence II | Leetcode 2901

class Solution {
    int hammingDistance(const string &a, const string &b) {
        int hamming_distance = 0;
        for (int i = 0, n = a.size(); i < n; ++i)
            if (a[i] != b[i])
                ++hamming_distance;
        return hamming_distance;
    }

public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int n = words.size();
        vector<int> lis(n, 1), parent(n, -1);

        int lis_len = 1, lis_end = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (groups[i] != groups[j]
                    && words[i].size() == words[j].size()
                    && hammingDistance(words[i], words[j]) == 1
                    && lis[i] + 1 > lis[j])
                {
                    lis[j] = lis[i] + 1;
                    parent[j] = i;
                    if (lis[j] > lis_len) {
                        lis_len = lis[j];
                        lis_end = j;
                    }
                }
            }
        }

        // reconstruct subsequence
        vector<string> ans;
        for (int cur = lis_end; cur != -1; cur = parent[cur])
            ans.push_back(words[cur]);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private int hammingDistance(String a, String b) {
        int distance = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                distance++;
            }
        }
        return distance;
    }

    public List<String> getWordsInLongestSubsequence(List<String> words, List<Integer> groups) {
        int n = words.size();
        int[] lis = new int[n];
        int[] parent = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(parent, -1);

        int lisLen = 1, lisEnd = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (groups.get(i) != groups.get(j) 
                    && words.get(i).length() == words.get(j).length() 
                    && hammingDistance(words.get(i), words.get(j)) == 1 
                    && lis[i] + 1 > lis[j]) {
                    lis[j] = lis[i] + 1;
                    parent[j] = i;
                    if (lis[j] > lisLen) {
                        lisLen = lis[j];
                        lisEnd = j;
                    }
                }
            }
        }

        // Reconstruct the subsequence
        List<String> ans = new ArrayList<>();
        for (int cur = lisEnd; cur != -1; cur = parent[cur]) {
            ans.add(words.get(cur));
        }
        Collections.reverse(ans);
        return ans;
    }
}

#Python
class Solution:
    def hammingDistance(self, a: str, b: str) -> int:
        return sum(1 for x, y in zip(a, b) if x != y)

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

        lis_len, lis_end = 1, 0
        for i in range(n):
            for j in range(i + 1, n):
                if (
                    groups[i] != groups[j]
                    and len(words[i]) == len(words[j])
                    and self.hammingDistance(words[i], words[j]) == 1
                    and lis[i] + 1 > lis[j]
                ):
                    lis[j] = lis[i] + 1
                    parent[j] = i
                    if lis[j] > lis_len:
                        lis_len = lis[j]
                        lis_end = j

        # Reconstruct the subsequence
        ans = []
        cur = lis_end
        while cur != -1:
            ans.append(words[cur])
            cur = parent[cur]
        return ans[::-1]
*/