最长交替子序列

题目描述

给定一个字符串数组 words 和一个二进制数组 groups，它们的长度均为 n，其中 words[i] 与 groups[i] 相关联。 你的任务是从 words 中选取最长的交替子序列。
交替子序列的定义是： 任意相邻的字符串，它们在 groups 数组中的值必须不同（即 groups[i] ≠ groups[i+1]）。 本质上，就是选择 words 的子序列，使得相邻的 groups 值不同。
形式化定义： 我们需要找到最长的索引子序列 [\(i_0, i_1, ..., i_{k-1}\)]，满足： \(group[i_j] \ne group[i_{j+1}] 0 \le j < k-1\)

然后返回对应的 words 子序列。 如果有多个答案，返回任意一个即可。 注意： words 中的字符串是互不相同的。

示例 1

输入：

eab
001

输出：

eb

解释：

一个可以选择的子序列是 eb，因为 groups[0] != groups[2]。
另一个可行的子序列是 ab，因为 groups[1] != groups[2]。 最长交替子序列的长度是 2。

示例 2

输入：

abcd
1011

输出：

abc

解释：

可选的子序列 abc，因为 groups[0] != groups[1]，groups[1] != groups[2]。
另一种可选方案是 abd，因为 groups[0] != groups[1]，groups[1] != groups[3]。
最长交替子序列的长度是 3。

约束

\(1 \le n == words.length == groups.length \le 100\)
\(1 \le words[i].length \le 10\)

groups[i] 仅包含 0 或 1
words 中的字符串互不相同
words[i] 仅包含小写英文字母。