LeetCode 522. 最长特殊序列 II
题目描述
原题：522. 最长特殊序列 II。
给定小写字符串列表，求一个字符串的子序列，它不能是列表中任何其它字符串的子序列，返回最大长度。不存在返回-1。重复的完整字符串也互相排除。
示例 1：
输入：strs = ["aba","cdc","eae"]
输出：3
解释："aba" 不是其余任何字符串的子序列，长度为 3。
示例 2：
输入：strs = ["aaa","aaa","aa"]
输出：-1
解释：两个 "aaa" 互相排除，"aa" 也是 "aaa" 的子序列，因此不存在符合要求的结果。
提示：
- 列表中的字符串只含小写英文字母。判断时其余每个位置的字符串都参与比较，内容完全相同的两个字符串也会互相排除。
题意分析
在字符串列表中，寻找一条子序列：它属于某个位置的字符串，却不是任何其他位置字符串的子序列，返回能够找到的最大长度。子序列保留字符顺序，但可以不连续，也可以取完整字符串。
这里必须排除其余所有位置，不能只找到某一个不包含它的字符串就算成功。重复的完整字符串虽然内容一样，仍是不同位置的输入，会互相排除。没有任何合法候选时返回
-1。
解法：逐个完整字符串做子序列排除
核心思路
[!blue]
只枚举每个完整输入字符串就够了。假设某个特殊子序列
T来自字符串S；如果S本身是另一字符串B的子序列，那么按照相同的字符顺序继续删去S中未被T选中的字符，T也会成为B的子序列，与特殊性矛盾。因此，存在特殊子序列的来源整串必然也特殊，而且长度不会更小。对每个位置
i，把strings[i]作为候选，与所有j != i的字符串逐个比较。只要候选是其中任意一个字符串的子序列，就将它淘汰；只有全部比较都没找到包含关系，才能用它的完整长度更新答案。子序列判断使用双指针。
i指向候选a下一次需要匹配的字符，扫描指针j从左到右经过容器串b。字符相同才推进候选指针，其他字符直接跳过；候选全部匹配成功就返回真，容器耗尽仍有未匹配字符则返回假。每次使用最早能匹配的位置是安全的：与选择更晚位置相比，前面匹配结果相同，却为剩余字符留下更长的后缀，不会减少后续匹配机会。因此无需回溯或保存所有匹配位置。
best保存已经找到的最大合法长度。若新候选长度不大于best，即使合法也不能改善结果，可以跳过；一旦发现包含它的其他字符串，也可以提前结束该候选的检查。相同内容的另一个位置会完整匹配，所以重复整串自然被排除，无需先做去重。
解题步骤
- 初始化
best = -1，逐个位置枚举完整字符串。- 长度不可能改善答案的候选直接跳过。
- 对所有其他位置，检查当前候选是否为对方的子序列，任意一次成功就淘汰候选。
- 没有被任何其他位置包含时，用候选长度更新答案。
- 返回
best。
代码实现
class Solution {
private boolean subsequence(String a, String b) {
int i = 0;
for (int j = 0; j < b.length() && i < a.length(); j++) {
if (a.charAt(i) == b.charAt(j)) {
i++;
}
}
return i == a.length();
}
public int findLUSlength(String[] strings) {
int best = -1;
for (int i = 0; i < strings.length; i++) {
if (strings[i].length() <= best) {
continue;
}
boolean valid = true;
for (int j = 0; j < strings.length; j++) {
if (i != j && subsequence(strings[i], strings[j])) {
valid = false;
break;
}
}
if (valid) {
best = strings[i].length();
}
}
return best;
}
}
func findLUSlength(strings []string) int {
subsequence := func(a, b string) bool {
i := 0
for j := 0; j < len(b) && i < len(a); j++ {
if a[i] == b[j] {
i++
}
}
return i == len(a)
}
best := -1
for i, a := range strings {
if len(a) <= best {
continue
}
valid := true
for j, b := range strings {
if i != j && subsequence(a, b) {
valid = false
break
}
}
if valid {
best = len(a)
}
}
return best
}
复杂度分析
- 时间复杂度：$O(n^2L)$，
n为字符串数量，L为最大长度。最坏枚举所有有序字符串对，每次子序列判断线性扫描对方字符串。- 空间复杂度：$O(1)$，只保存下标、匹配进度、合法标记与当前最大长度，不修改输入。
关键点总结
[!green]
- 子序列关系具有传递性，保证最优答案可以直接取某个完整输入串。
- 合法候选必须不被任何其他位置包含，重复内容也要参与排除。
- 双指针优先使用最早匹配位置，为剩余字符保留尽可能多的空间。
易错点总结
[!yellow]
- 按字符串内容而不是按下标判断“其他字符串”，会忽略重复内容之间的排除关系。
- 找到一个不包含候选的字符串就立即接受，未检查其他字符串可能仍然包含它。
- 将子序列判断方向反过来，检查较短的其他串能否进入候选，不能判断候选是否特殊。
- 先把相同字符串去重，会让本来被重复输入排除的候选错误变成合法。
- 用连续子串匹配代替子序列匹配，会漏掉允许跳过字符的包含关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 521. 最长特殊序列 Ⅰ | 简单 | 两个字符串时能简化为相等判断，多字符串时要排除被任何其他串包含的候选。 |
| 392. 判断子序列 | 简单 | 复用双指针判断子序列，作为筛除完整候选的基本操作。 |