题目描述

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

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."

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

样例

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

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

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串（"z"、"a"、"b"、"za"、"ab"、和 "zab"）在 base 中出现。

限制

• 1 <= s.length <= 10^5
• s 由小写英文字母组成。

算法

(双指针滑动窗口 + 分类统计) $O(n)$

1. 很容易想到，可以将字符串 s 表示为若干段 最长 的合法子串的组合 $s_1, s_2, \dots, s_k$。每一段 最长 的合法子串 $s_i$ 的含义为 $s_i$ 的所有子串都在 base 中出现过。
2. 若题目不要求无重复，此时可以直接统计出现在 s 中的子串数量。$s_i$ 贡献答案的数量为从到 $1 + 2 + \dots + len(s_i)$。
3. 题目要求去重，观察到子串可以根据开头字母进行分类，最多有 26 个字母，所以最多有 26 类。如果我们能得到每个字母开头所能得到子串的最大长度，那么该字母开头贡献的答案子串个数就是这个最大长度。
4. 所以在第一步拆分的过程中，每拆分出一段 $s_i$，就对 $s_i$ 子串中，统计每个字母开头到 $s_i$ 末尾的长度，和之前记录的长度取最大值。

时间复杂度

• 通过双指针滑动窗口，拆分的时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        const int n = s.size();
        vector<int> bucket(26, 0);

        int last = 0;
        for (int i = 1; i < n; i++) {
            if (!(s[i] - s[i - 1] == 1 || s[i] - s[i - 1] == -25)) {
                // 拆分出一段进行分类统计。
                for (int j = last; j < i; j++)
                    // 统计当前每个字母开头得到的长度，并和之前记录的最大长度取最大值。
                    bucket[s[j] - 'a'] = max(bucket[s[j] - 'a'], i - j);
                last = i;
            }
        }
        for (int j = last; j < n; j++)
            bucket[s[j] - 'a'] = max(bucket[s[j] - 'a'], n - j);

        return accumulate(bucket.begin(), bucket.end(), 0);
    }
};