Longest Unequal Adjacent Groups Subsequence I

Leetcode Problem:

• Longest Unequal Adjacent Groups Subsequence I

Summary

• The problem is to find the longest alternating subsequence from a given array of words and a binary array groups.

Approach

• The solution uses a simple iterative approach to find the longest alternating subsequence
• It initializes a variable toggle to the opposite of the first group value
• Then it iterates over the groups array, adding words to the result vector if the current group value is different from the toggle value
• The toggle value is updated accordingly.

Complexity

• O(n)

Explanation

• The time complexity of this solution is O(n) because it only needs to iterate over the groups array once
• The space complexity is also O(n) because in the worst case, it needs to store all words in the result vector.

Solution Code:

class Solution {
public:
    vector getLongestSubsequence(vector& words, vector& groups) {
        int toggle = groups[0] ^ 1;
        vector ans;
        for(int i = 0 ; i < groups.size(); i++){
            if(toggle != groups[i]){
                ans.push_back(words[i]);
                toggle ^= 1;
            }
        }
        return ans;
    }
};