2900. Longest Unequal Adjacent Groups Subsequence I

You are given an integer n, a 0-indexed string array words, and a 0-indexed binary array groups, both arrays having length n.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i0, i1, ..., ik - 1] having length k, groups[ij] != groups[ij + 1], for each j where 0 < j + 1 < k.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

A subsequence of an array is a new array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Note: strings in words may be unequal in length.

class Solution {
public:
    vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
        unordered_map<int, int> best;
        unordered_map<int, int> at;
        vector<int> go(n);
        int pick = -1;
        for(int i = 0; i < n; i++) {
            int who = -1;
            for(auto& [k,v] : best) {
                if(k == groups[i]) continue;
                if(who == -1) who = k;
                else {
                    if(best[who] < v) who = k;
                }
            }
            if(who == -1) {
                go[i] = -1;
                best[groups[i]] = 1;
                at[groups[i]] = i;
            } else {
                go[i] = at[who];
                best[groups[i]] = best[who] + 1;
                at[groups[i]] = i;
            }
            if(best[groups[i]] > best[pick]) pick = groups[i];
        }
        vector<string> res;
        int p = at[pick];
        while(p != -1) {
            res.push_back(words[p]);
            p = go[p];
        }
        reverse(begin(res), end(res));
        return res;
    }
};