What is the primary approach to solving the Longest Unequal Adjacent Groups Subsequence II problem?

The primary approach involves dynamic programming, where you track the longest subsequence ending at each word while ensuring the Hamming distance and group constraints are met.

How does the Hamming distance affect the subsequences in this problem?

The Hamming distance ensures that consecutive words in the subsequence are different at least at one position. This is a crucial condition for forming valid subsequences.

What does the dynamic programming state transition involve?

For each word, check all previous words to see if they can form a valid subsequence based on group differences and the Hamming distance.

How do group constraints impact the subsequence?

Group constraints ensure that no two consecutive words in the subsequence belong to the same group, adding an extra layer of restriction to the subsequences.

What is the time complexity of solving the Longest Unequal Adjacent Groups Subsequence II?

The time complexity is O(n^2L), where n is the number of words, and L is the average length of the words.

#2901

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长相邻不相等子序列 II

给定一个字符串数组 words ，和一个数组 groups ，两个数组长度都是 n 。两个长度相等字符串的汉明距离定义为对应位置字符不同的数目。你需要从下标 [0, 1, ..., n - 1] 中选出一个最长子序列，将这个子序列记作长度为 k 的 [i 0 , i 1 , ...…

数组字符串动态规划

题目描述

给定一个字符串数组 words ，和一个数组 groups ，两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符不同的数目。

你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i₀, i₁, ..., i_{k - 1}] ，它需要满足以下条件：

相邻下标对应的 groups 值不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[i_j] != groups[i_{j + 1}] 。
对于所有 0 < j + 1 < k 的下标 j ，都满足 words[i_j] 和 words[i_{j + 1}] 的长度相等，且两个字符串之间的 汉明距离 为 1 。

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

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

示例 1：

输入：words = ["bab","dab","cab"], groups = [1,2,2]
输出：["bab","cab"]
解释：一个可行的子序列是 [0,2] 。
- groups[0] != groups[2]
- words[0].length == words[2].length 且它们之间的汉明距离为 1 。
所以一个可行的答案是 [words[0],words[2]] = ["bab","cab"] 。
另一个可行的子序列是 [0,1] 。
- groups[0] != groups[1]
- words[0].length = words[1].length 且它们之间的汉明距离为 1 。
所以另一个可行的答案是 [words[0],words[1]] = ["bab","dab"] 。
符合题意的最长子序列的长度为 2 。

示例 2：

输入：words = ["a","b","c","d"], groups = [1,2,3,4]
输出：["a","b","c","d"]
解释：我们选择子序列 [0,1,2,3] 。
它同时满足两个条件。
所以答案为 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"] 。
它是所有下标子序列里最长且满足所有条件的。
所以它是唯一的答案。

提示：

1 <= n == words.length == groups.length <= 1000
1 <= words[i].length <= 10
1 <= groups[i] <= n
words 中的字符串 互不相同 。
words[i] 只包含小写英文字母。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的长度，定义 $g[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的前驱下标。初始时 $f[i] = 1$ , $g[i] = -1$ 。

另外，我们定义一个变量 $mx$ 表示最长相邻不相等子序列的长度。

我们枚举 $i$ ，枚举 $j \in [0, i)$ ，如果 $groups[i] \neq groups[j]$ 且 $f[i] \lt f[j] + 1$ 且 $words[i]$ 和 $words[j]$ 之间的汉明距离为 $1$ ，则更新 $f[i] = f[j] + 1$ ， $g[i] = j$ ，并且更新 $mx = \max(mx, f[i])$ 。

最后，我们从 $f$ 数组中找到最大值对应的下标 $i$ ，然后从 $i$ 开始不断往前找，直到找到 $g[i] = -1$ ，这样就找到了最长相邻不相等子序列。

时间复杂度 $O(n^2 \times L)$ ，空间复杂度 $O(n)$ 。其中 $L$ 表示单词的最大长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def getWordsInLongestSubsequence(
        self, words: List[str], groups: List[int]
    ) -> List[str]:
        def check(s: str, t: str) -> bool:
            return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1

        n = len(groups)
        f = [1] * n
        g = [-1] * n
        mx = 1
        for i, x in enumerate(groups):
            for j, y in enumerate(groups[:i]):
                if x != y and f[i] < f[j] + 1 and check(words[i], words[j]):
                    f[i] = f[j] + 1
                    g[i] = j
                    mx = max(mx, f[i])
        ans = []
        for i in range(n):
            if f[i] == mx:
                j = i
                while j >= 0:
                    ans.append(words[j])
                    j = g[j]
                break
        return ans[::-1]

speed

复杂度分析

指标	值
时间	O(n^2L)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands dynamic programming and state transitions.
question_mark
Able to manage group constraints and Hamming distance in the context of subsequences.
question_mark
Efficient in applying the dynamic programming approach to solve sequence problems.

warning

常见陷阱

外企场景

error
Forgetting to check the group numbers for adjacent subsequence elements.
error
Not handling edge cases with words that are identical or have zero Hamming distance.
error
Not updating `dp[i]` correctly when a valid subsequence is found.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow subsequences where group numbers can be equal.
arrow_right_alt
Change the minimum required Hamming distance between consecutive words.
arrow_right_alt
Modify the problem to find the shortest subsequence instead of the longest.

help

常见问题

外企场景

继续练习

#2900 最长相邻不相等子序列 I #2977 转换字符串的最小成本 II #2746 字符串连接删减字母