3104：查找最长的自包含子串（★★）

Ian

2024-04-06 约 521 字预计阅读 2 分钟次阅读

力扣第 3104 题

题目

给定字符串 s，你需要找到 s 的 最长自包含 子串的长度。

如果 s 的一个子串 t 满足 t != s 且 t 中的每一个字符在 s 的剩余部分都不存在，则被称为是 自包含 的。

如果存在 s 的最长自包含子串，返回它的长度，否则返回 -1。

示例 1：

输入：s = "abba"

输出：2

解释：
让我们检查子串 "bb"。你可以发现子串外没有其它 "b"。因此答案为 2。

示例 2：

输入：s = "abab"

输出：-1

解释：
我们选择的每一个子串都不满足描述的特点（子串内外包含有一些字母）。所以答案是 -1。

示例 3：

输入：s = "abacd"

输出：4

解释：
让我们检查子串 "abac"。子串之外只有一个字母 "d"。子串内没有 "d"，所以它满足条件并且答案为 4。

提示：

2 <= s.length <= 5 * 10⁴
s 只包含小写英文字母。

相似问题：

3458：选择 K 个互不重叠的特殊子字符串（2220 分）

分析

先统计每个字符的区间及个数 l,r,s，得到数组 A
A 按左端点排序，自包含子串必然对应 A 的子数组
对于 A 的某个子数组，若 max(r)-min(l)+1=sum(s)<n，即是一个自包含子串

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def maxSubstringLength(self, s: str) -> int:
        n = len(s)
        A = [ord(c)-ord('a') for c in s]
        d = [[] for _ in range(26)]
        for i,a in enumerate(A):
            d[a].append(i)
        A = [[B[0],B[-1],len(B)] for B in d if B]
        A.sort()
        res = -1
        for i,(l,r,s) in enumerate(A):
            if r-l+1==s<n:
                res = max(res,s)
            for _,r2,s2 in A[i+1:]:
                r,s = max(r,r2),s+s2
                if r-l+1==s<n:
                    res = max(res,s)
        return res

99 ms

目录

3104：查找最长的自包含子串（★★）

题目

分析

解答