2900. Longest Unequal Adjacent Groups Subsequence I LeetCode Solution

In this guide, you will get 2900. Longest Unequal Adjacent Groups Subsequence I LeetCode Solution with the best time and space complexity. The solution to Longest Unequal Adjacent Groups Subsequence I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Longest Unequal Adjacent Groups Subsequence I solution in C++
4. Longest Unequal Adjacent Groups Subsequence I solution in Java
5. Longest Unequal Adjacent Groups Subsequence I solution in Python
6. Additional Resources

Problem Statement of Longest Unequal Adjacent Groups Subsequence I

You are given a string array words and a binary array groups both of length n, where words[i] is associated with groups[i].
Your task is to select the longest alternating subsequence from words. A subsequence of words is alternating if for any two consecutive strings in the sequence, their corresponding elements in the binary array groups differ. Essentially, you are to choose strings such that adjacent elements have non-matching corresponding bits in the groups array.
Formally, you need to find the longest subsequence of an array of indices [0, 1, …, n – 1] denoted as [i0, i1, …, ik-1], such that groups[ij] != groups[ij+1] for each 0 <= j < k – 1 and then find the words corresponding to these indices.
Return the selected subsequence. If there are multiple answers, return any of them.
Note: The elements in words are distinct.

Example 1:

Input: words = [“e”,”a”,”b”], groups = [0,0,1]
Output: [“e”,”b”]
Explanation: A subsequence that can be selected is [“e”,”b”] because groups[0] != groups[2]. Another subsequence that can be selected is [“a”,”b”] because groups[1] != groups[2]. It can be demonstrated that the length of the longest subsequence of indices that satisfies the condition is 2.

Example 2:

Input: words = [“a”,”b”,”c”,”d”], groups = [1,0,1,1]
Output: [“a”,”b”,”c”]
Explanation: A subsequence that can be selected is [“a”,”b”,”c”] because groups[0] != groups[1] and groups[1] != groups[2]. Another subsequence that can be selected is [“a”,”b”,”d”] because groups[0] != groups[1] and groups[1] != groups[3]. It can be shown that the length of the longest subsequence of indices that satisfies the condition is 3.

Constraints:

1 <= n == words.length == groups.length <= 100
1 <= words[i].length <= 10
groups[i] is either 0 or 1.
words consists of distinct strings.
words[i] consists of lowercase English letters.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2900. Longest Unequal Adjacent Groups Subsequence I LeetCode Solution in C++

class Solution {
 public:
  vector<string> getWordsInLongestSubsequence(int n, vector<string>& words,
                                              vector<int>& groups) {
    vector<string> ans;
    int groupId = -1;

    for (int i = 0; i < n; ++i)
      if (groups[i] != groupId) {
        groupId = groups[i];
        ans.push_back(words[i]);
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

2900. Longest Unequal Adjacent Groups Subsequence I LeetCode Solution in Java

class Solution {
  public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
    List<String> ans = new ArrayList<>();
    int groupId = -1;

    for (int i = 0; i < n; ++i)
      if (groups[i] != groupId) {
        groupId = groups[i];
        ans.add(words[i]);
      }

    return ans;
  }
}
// code provided by PROGIEZ

2900. Longest Unequal Adjacent Groups Subsequence I LeetCode Solution in Python

class Solution:
  def getWordsInLongestSubsequence(
      self,
      n: int,
      words: list[str],
      groups: list[int],
  ) -> list[str]:
    ans = []
    groupId = -1

    for word, group in zip(words, groups):
      if group != groupId:
        groupId = group
        ans.append(word)

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.