2900. 最长相邻不相等子序列 I

题目链接

2900. 最长相邻不相等子序列 I - 力扣（LeetCode）

题目描述

给你一个下标从 0 开始的字符串数组words，和一个下标从 0 开始的 二进制 数组groups，两个数组长度都是n。

你需要从words中选出 最长子序列。如果对于序列中的任何两个连续串，二进制数组groups中它们的对应元素不同，则words的子序列是不同的。

正式来说，你需要从下标[0, 1, ..., n - 1]中选出一个 最长子序列 ，将这个子序列记作长度为k的[i0, i1, ..., ik - 1]，对于所有满足0 <= j < k - 1的j都有groups[ij] != groups[ij + 1]。

请你返回一个字符串数组，它是下标子序列 依次 对应words数组中的字符串连接形成的字符串数组。如果有多个答案，返回 任意 一个。

注意：words中的元素是不同的 。

题目示例

示例 1 :

输入：words = ["e","a","b"], groups = [0,0,1] 输出：["e","b"] 解释：一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。 所以一个可行的答案是 [words[0],words[2]] = ["e","b"] 。 另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。 得到答案为 [words[1],words[2]] = ["a","b"] 。 这也是一个可行的答案。 符合题意的最长子序列的长度为 2

示例 2 :

输入：words = ["a","b","c","d"], groups = [1,0,1,1] 输出：["a","b","c"] 解释：一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。 所以一个可行的答案是 [words[0],words[1],words[2]] = ["a","b","c"] 。 另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。 得到答案为 [words[0],words[1],words[3]] = ["a","b","d"] 。 这也是一个可行的答案。 符合题意的最长子序列的长度为 3 。

解题思路

1. 问题理解：
   • 给定一个字符串数组words和一个整数数组groups，其中groups[i]表示words[i]的分组。
   • 需要找到一个子序列，使得相邻元素的group值不同，并且这个子序列是最长的。
2. 关键思路：
   • 贪心选择：为了构造最长的满足条件的子序列，我们只需要保证相邻元素的group值不同即可。
   • 遍历数组：对于每个元素，如果它是最后一个元素，或者它的group值与下一个元素不同，就将其加入结果列表。
   • 跳过连续相同group的元素：这样可以保证结果子序列中相邻元素的group值不同。
3. 算法流程：
   • 初始化一个空列表ans用于存储结果。
   • 遍历words和groups数组：
     • 如果当前元素是最后一个，或者当前group值与下一个不同，则将当前word加入ans。
   • 返回ans作为结果

题解代码

classSolution{publicList<String>getLongestSubsequence(String[]words,int[]groups){List<String>ans=newArrayList<>();// 存储最终结果intn=groups.length;// 数组长度// 遍历所有元素for(inti=0;i<n;i++){// 如果当前元素是最后一个，或者当前元素与下一个元素的group值不同if(i==n-1||groups[i]!=groups[i+1]){ans.add(words[i]);// 将当前word加入结果列表}}returnans;}}

复杂度分析

1. 时间复杂度：
   • 遍历数组一次：O(n)，其中n是数组的长度。
   • 总时间复杂度：O(n)。
2. 空间复杂度：
   • 存储结果的列表ans：最坏情况下需要O(n)空间（当所有相邻group都不同时）。
   • 总空间复杂度：O(n)。