难度: Medium
定义字符串 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运行时间: 62 ms
内存: 0.0 MB
class Solution:
def findSubstringInWraproundString(self, s: str) -> int:
b = 0
c = [0] * 26
s = tuple(map(lambda c: ord(c) - 97, s))
c[s[0]] = 1
for i in range(1, len(s)):
if (s[i]) - (s[i - 1]) not in (1, -25):
if c[s[b]] < (m := i - b): c[s[b]] = m
b = i
# if not c[s[b]]: c[s[b]] = 1
if c[s[b]] < (m := len(s) - b): c[s[b]] = m
b = c.index(max(c))
for i in range(b - 25, b):
if c[i - 1] - 1 > c[i]: c[i] = c[i - 1] - 1
return sum(c)
这个题解的思路是使用一个长度为26的数组c来记录以每个字母结尾的最长连续子串的长度。遍历字符串s，如果当前字符和前一个字符的ASCII码差为1或-25（说明是相邻的字母），则继续维护当前的连续子串；否则，更新数组c中对应字母的最大长度，并重新开始一个新的连续子串。最后，从后往前遍历数组c，如果前一个字母的最长子串长度比当前字母的最长子串长度大1，则更新当前字母的最长子串长度。最终数组c中的所有元素之和即为所求的不同非空子串的数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findSubstringInWraproundString(self, s: str) -> int:
b = 0 # 记录当前连续子串的起始位置
c = [0] * 26 # 记录以每个字母结尾的最长连续子串的长度
s = tuple(map(lambda c: ord(c) - 97, s)) # 将字符串s转换为ASCII码列表
c[s[0]] = 1 # 初始化以第一个字母结尾的最长连续子串长度为1
for i in range(1, len(s)):
if (s[i]) - (s[i - 1]) not in (1, -25): # 如果当前字符和前一个字符不是相邻的字母
if c[s[b]] < (m := i - b): c[s[b]] = m # 更新以当前连续子串起始字母结尾的最长连续子串长度
b = i # 更新连续子串的起始位置
if c[s[b]] < (m := len(s) - b): c[s[b]] = m # 处理最后一个连续子串
b = c.index(max(c)) # 找到最长连续子串的结尾字母
for i in range(b - 25, b): # 从后往前遍历数组c
if c[i - 1] - 1 > c[i]: c[i] = c[i - 1] - 1 # 如果前一个字母的最长子串长度比当前字母的最长子串长度大1，则更新当前字母的最长子串长度
return sum(c) # 返回数组c中所有元素之和，即为所求的不同非空子串的数量
题解中使用数组c来记录以每个字母结尾的最长连续子串的长度。字符的循环性，即从'z'到'a'的过渡，是通过检查当前字符和前一个字符的ASCII码差值来处理的。如果差值为1，表示两个字符是顺序相邻的；如果差值为-25，表示这是从'z'到'a'的过渡。这种方式使得算法能够正确处理环绕（从'z'回到'a'）的情况，符合题目中'环绕字符串'的要求。
当当前字符和前一个字符不是相邻的，这意味着当前的连续子串已经结束，不能再继续延伸。此时，需要更新连续子串的起始位置以开始一个新的子串计算。这样的更新确保了每个连续子串都被正确地记录，并且其长度只被计算一次。这对结果的正确性是必要的，因为它保证了每个以不同字母结尾的最长连续子串都能被正确地更新和记录。
从后往前遍历数组c并更新元素的主要目的是确保每个字符的子串长度都是最大可能的。特别是对于环绕的场景，如从'z'回到'a'，这种更新方法可以确保前一个字母的最长子串长度能正确影响到后一个字母。这种从后往前的更新方法能够确保所有可能的连续子串都被考虑到，从而帮助我们正确计算出不同非空子串的总数量。
在处理最后一个连续子串时直接更新数组c，这样做是为了确保此子串能被计入统计。算法在更新数组c时会检查当前记录是否小于新计算出的连续子串长度，只有当新的长度更大时才进行更新。这样的处理方式不会导致结果出错，因为它遵循了始终记录最长连续子串长度的原则，确保了每个以不同字母结尾的子串长度都是最大可能的。