最长特殊序列 II 图解题解

特殊序列凭什么算特殊，要返回什么

给一个字符串列表 strs，要找出里面最长的「特殊序列」的长度。特殊序列指某个串独有的子序列，也就是它不是其它任何串的子序列。子序列就是删掉原串里若干字符、剩下的按原顺序拼起来，不要求连续。题面例子 strs=["aba","cdc","eae"] 三个串互不为子序列，答案是最长的 3；strs=["aaa","aaa","aa"] 每个串都被别人包含，返回 -1。

为什么不能直接挑最长的串交上去

直觉是把最长的串直接交上去：它最长，总不会是更短串的子序列。可这招碰上重复串就漏。strs=["aaa","aaa","aa"] 里最长的是 "aaa"，但另一个 "aaa" 和它一模一样、互为子序列，谁都不独有，长度并列第一也照样淘汰。长度只是候选资格，真正要判的是有没有被别人包含，得挨个比。

怎么判一个串是不是另一个串的子序列

判断「s 是不是 t 的子序列」用双指针，两个下标各扫一个串。i 指 s、j 指 t，都从 0 起。看 t[j]：正好是 s 当前要找的 s[i]，这一位就对上，i 挪一格找下一个；对不上，i 不动，只让 j 右移接着找。t 扫完时若 i 已走到 s 末尾（i 等于 s 的长度），说明 s 每个字符都按顺序在 t 里出现过，s 就是 t 的子序列。一个串只要被任意别的串包含就出局，所以两两各判一次即可。

整个流程是怎么把答案挑出来的

主流程两层循环：外层把每个串轮流当候选 s，内层拿它和其余串 t 逐个判子序列，要跳过自己（下标 i≠j，因为任何串都是自身的子序列，不跳过必被自己判掉）。s 被某个 t 包含就没戏，换下一个候选；一路比到底没被任何串包含，它就是特殊序列，用长度更新答案最大值。全部走完，答案初值 -1 要么被刷新过、要么原样保持。

题面两组数据，逐个候选试一遍

先看 strs=["aba","cdc","eae"]。候选 "aba" 比 "cdc"：c、d、c 里找不到打头的 a，i 停在 0，不是子序列；再比 "eae"，只有中间那个 a 对上一个，走完 i 没到 3，也不是。都没包含它，"aba" 特殊，答案 3；另外两个同理各自独有。

再看 strs=["aaa","aaa","aa"]。第一个 "aaa" 比第二个 "aaa"，三个 a 全对上、i 走到 3，被包含淘汰；第二个同样被第一个吃掉；"aa" 比 "aaa" 也全中被包含。三个全出局，答案保持 -1。

跳过自己没写、子序列错当子串，会怎样

内层忘了 i≠j 这道跳过自己的关卡，每个串都会先被自己判成子序列，没有一个能活下来，答案永远卡在 -1。把「子序列」错当成连续「子串」也常见："aa" 是 "aba" 的子序列（取第 0、2 位两个 a），却不是连续子串，用子串的判法会把本该淘汰的串误放进来。别被「最长」带偏，两个相同的最长串会互相抵消，长度再大也不算数。

复杂度上，n 个串两两配对 O(n²)，每对再做一次 O(L) 子序列扫描（L 为串长），合起来 O(n²·L)；只用 i、j 两个下标和一个记分变量，空间 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(s: str, t: str):
            i = j = 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)

        ans = -1
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and check(s, t):
                    break
            else:
                ans = max(ans, len(s))
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        int n = strs.size();
        auto check = [&](const string& s, const string& t) {
            int m = s.size(), n = t.size();
            int i = 0;
            for (int j = 0; i < m && j < n; ++j) {
                if (s[i] == t[j]) {
                    ++i;
                }
            }
            return i == m;
        };
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].size();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = max(ans, x);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        int n = strs.length;
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].length();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = Math.max(ans, x);
        }
        return ans;
    }

    private boolean check(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0;
        for (int j = 0; i < m && j < n; ++j) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
        }
        return i == m;
    }
}