最长相邻不相等子序列 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:

Example 2:

 

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.

/* 
思路：
1. 使用Stream API处理数组，初始思路与传统Java方法类似。
2. 遍历数组 words 和 groups，通过条件过滤和收集处理符合条件的子序列。
3. 返回最长的子序列。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SolutionStream {
    public static List<String> longestSubsequence(String[] words, int[] groups) {
        return IntStream.range(0, words.length)
                .mapToObj(i -> IntStream.range(i, words.length)
                        .filter(j -> j == i || groups[j] != groups[j - 1])
                        .mapToObj(j -> words[j])
                        .collect(Collectors.toList()))
                .max((list1, list2) -> list1.size() - list2.size())
                .orElse(new ArrayList<>());
    }

    public static void main(String[] args) {
        String[] words = {"e", "a", "b"};
        int[] groups = {0, 0, 1};
        System.out.println(longestSubsequence(words, groups)); // 输出: ["e", "b"]
    }
}

该题解的核心思路是遍历groups数组，并构建一个索引列表arr，用于记录符合条件的words的索引。初始时，arr包含第一个元素的索引0，表示至少包含words的第一个元素。之后，遍历groups数组，只要当前元素与arr列表中最后一个记录的索引对应的groups值不同，就将当前索引添加到arr中。这样，arr中存储的索引对应的groups值必然是交替变化的，满足题目要求的连续不相等条件。最终，根据arr中的索引，提取words数组中对应的字符串，形成所求的最长子序列。

O(n)

O(n)