0467：环绕字符串中唯一的子字符串（★）

力扣第 467 题

题目

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

示例 1：

输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

分析

• 容易想到递推以 s[i] 结尾的最长符合子串
• 但这样存在重复计算的问题，比如 ‘cac’ 中 ‘c’ 会被计算两次
• 所以对相同字符结尾的，只取最大值即可

解答

1
2
3
4
5
6
7
8

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        A = [ord(c)-ord('a') for c in s]
        f,w = [0]*26,0
        for i,a in enumerate(A):
            w = w+1 if i and (a-A[i-1])%26==1 else 1
            f[a] = max(f[a],w)
        return sum(f)

87 ms