2901: Longest-Unequal-Adjacent-Groups-Subsequence-II
Medium

table of contents

This question is just a dynamic programming question.

My first thought is, for any index i, if the longest subsequence that ends at the index i is greater than 1, then the previous word must be located in words at an index value between [0, i). However, then the problem is, how do you know how many previous words existed in this specific sequence of words.

We can do this using an array of size n that I called dp. In it, at each index i, we hold the:

Then, at index i, we can simply check which of the elements at indices smaller than i have a hamming distance of 1. Now, using the dp array, we can determine which subsequence (ending at indices containing values with a hamming distance of 1 to i) we want to append words[i] to (the longest one) and the index of the previous element.

Finally, we can simply just repeat this until we reach the element and backtrack from the tail-end of the longest subsequence.

code

struct dpElement {
    int maxSubsequenceLength;
    int prevElementIndex;
    dpElement(int length = -1, int prev = -1)
      : maxSubsequenceLength(length), prevElementIndex(prev) { }
};
class Solution {
public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        vector<dpElement> dp (words.size());

        int maxSubsequenceLength{1};
        int maxSubsequenceIndex{0};

        dp[0] = dpElement(1, -1);
        for (int i = 1; i < words.size(); ++i) {
            dpElement tempElement = dpElement();
            for (int j = 0; j < i; ++j) {
                if (groups[i] == groups[j]) continue;
                if (dp[j].maxSubsequenceLength < tempElement.maxSubsequenceLength) continue;
                if (words[i].size() != words[j].size()) continue;

                int diff = 0;
                for (int k = 0; diff < 2 && k < min(words[i].size(), words[j].size()); ++k) {
                    if (words[i][k] != words[j][k]) {
                        ++diff;
                    }
                }

                if (diff < 2) {
                    tempElement.prevElementIndex = j;
                    tempElement.maxSubsequenceLength = dp[j].maxSubsequenceLength+1;
                }
            }
            if (tempElement.maxSubsequenceLength > maxSubsequenceLength) {
                maxSubsequenceLength = tempElement.maxSubsequenceLength;
                maxSubsequenceIndex = i;
            }
            if (tempElement.maxSubsequenceLength == -1) tempElement.maxSubsequenceLength = 1;
            dp[i] = tempElement;
        }

        vector<string> ans (maxSubsequenceLength);

        for (int i = maxSubsequenceLength-1; i >= 0; --i) {
            ans[i] = words[maxSubsequenceIndex];
            maxSubsequenceIndex = dp[maxSubsequenceIndex].prevElementIndex;
        }

        return ans;
    }
};

complexity