Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7

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.

Solution

Method 1 - Greedy

To solve this:

  • Use a greedy approach to iterate through the array.
  • Choose an element only if the alternating condition between its group and the previous group’s value is met.
  • Keep track of the selected subsequence in an auxiliary list.

Algorithm

  1. Start iterating through the array with a prev variable to track the last selected group’s value.
  2. Add the first element to the subsequence since there are no previous elements.
  3. If the current group’s value differs from prev, include the element in the subsequence and update prev.
  4. Continue this until the end of the array.
  5. Return the selected subsequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public List<String> getLongestSubsequence(String[] words, int[] groups) {
        List<String> ans = new ArrayList<>();
        int prevGroup = -1; // Initialize prevGroup to -1 (non-existent in groups)
        
        for (int i = 0; i < words.length; i++) {
            if (groups[i] != prevGroup) { // Check if alternating condition is satisfied
                ans.add(words[i]);
                prevGroup = groups[i]; // Update previous group to current group's value
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def get_longest_subsequence(self, words: List[str], groups: List[int]) -> List[str]:
        ans: List[str] = []
        prev_group: int = -1  # Initialize `prev_group` to a value not in groups 
        
        for i, word in enumerate(words):
            if groups[i] != prev_group:  # Check if alternating condition is satisfied
                ans.append(word)
                prev_group = groups[i]  # Update previous group to current group's value
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) because we only iterate through the array once.
  • 🧺 Space complexity: O(k) where k is the size of the resulting subsequence, which is at most n.