LeetCode 2900: Longest Unequal Adjacent Groups Subsequence I

Explanation

To solve this problem, we can iterate through the words and groups simultaneously, keeping track of the current longest alternating subsequence. We maintain two variables: maxLen to store the length of the longest alternating subsequence found so far, and result to store the actual subsequence.

We iterate through the words and groups, checking if the current word and the next word have different group values. If they do, we increment the current length and update the result accordingly. If they have the same group value, we reset the current length to 1.

Finally, we return the resulting subsequence.

• Time complexity: O(n) where n is the number of words/groups.
• Space complexity: O(1) as we are only storing a constant number of variables.

class Solution {
    public List<String> longestSubsequence(String[] words, int[] groups) {
        List<String> result = new ArrayList<>();
        int maxLen = 0;
        int currLen = 1;

        for (int i = 0; i < words.length - 1; i++) {
            if (groups[i] != groups[i + 1]) {
                currLen++;
                if (currLen > maxLen) {
                    maxLen = currLen;
                    result.clear();
                    result.add(words[i]);
                    result.add(words[i + 1]);
                }
            } else {
                currLen = 1;
            }
        }

        return result;
    }
}