Untitled

class Solution {
public:
    int dis(string& a, string& b)
    {
        int diff = 0;
        for(int i = 0; i < a.size(); ++i)
        {
            if(a[i]!=b[i])
                ++diff;
        }
        return diff;
    }
    
    vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {

        vector<string> res;
        vector<pair<int, int>> dp;

        for(int i = 0; i < n; ++i)
        {
            dp.push_back({0, -1});
            for(int j = i - 1; j >= 0; --j)
            {
                if(words[i].size() == words[j].size() && dis(words[i], words[j]) == 1 && groups[i] != groups[j])
                {
                    if(dp[j].first >= dp[i].first)
                        dp[i] = {dp[j].first + 1, j};
                }
            }
        }
        int a = INT_MIN, ind = -1;
        for(int i = 0; i < n; ++i)
        {
            if(dp[i].first > a)
            {
                a= dp[i].first;
                ind = i;
            }
        }
        
        while(ind != -1)
        {
            res.push_back(words[ind]);
            ind = dp[ind].second;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};