467. 环绕字符串中唯一的子字符串

题目

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….” .
现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。

示例 1:

输入: p = “a”
输出: 1
解释: 字符串 s 中只有一个”a”子字符。

示例 2:

输入: p = “cac”
输出: 2
解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。

示例 3:

输入: p = “zab”
输出: 6
解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

提示:

1 <= p.length <= 10^5
p 由小写英文字母构成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

如果不要求「唯一」，题目其实求的就是每一个字母连续的子串的长度，比如”zabchi”，”zabc”和”hi”都是连续的子串，答案就是这两个字符串的子串个数，每一个字符串的子串个数为%2F2#card=math&code=n%28n%2B1%29%2F2&id=veXQR)，因此这个例子的答案就是。

但题目要求子串唯一，例如对于”zabchibcd”来说，如果仍按上面的方式，会重复”bc”这部分的数目。

如何去重？其实前面的思路中的%2F2#card=math&code=n%28n%2B1%29%2F2&id=JfAic)就是从1加到n，分别对应以每个字符结尾的子串个数，对于”zabc”，以z a b c结尾的子串分别为1 2 3 4个，当再遇到后面的字符b和c，以新的b和c结尾的子串个数（1和2）就不应该被计算在内。

因此，记录以每个字符结尾的连续的最长的子串长度，即可实现去重。然后最后再去累加答案。

代码

class Solution {
    public int findSubstringInWraproundString(String p) {
        int n = p.length();
        int ans = 0;
        int cnt = 1;
        int[] maxLen = new int[26];
        maxLen[p.charAt(0) - 'a'] = 1;
        for (int i = 1; i < n; i++) {
            int k = p.charAt(i) - 'a';
            if ((p.charAt(i) - p.charAt(i - 1) + 26) % 26 == 1) {
                cnt++;
            } else {
                cnt = 1;
            }
            maxLen[k] = Math.max(cnt, maxLen[k]);
        }
        for (int i = 0; i < 26; i++) {
            ans += maxLen[i];
        }
        return ans;
    }
}