1.题目描述

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”。

2.思路

2.1 代码

题目要求在字符串中找到连续子数组个数，其实就是在遍历数组时，求以当前字符结尾的连续子串长度，然后再把数组中每一位对应的子串长度加起来求和便是最终答案。这里一下几点需要注意：

1. 重复字符的问题。出现重复字符时，对比子串长度，以最长的为结果，并最终结果只计算一次；
2. 题目使用环形字符串，因此当遍历到 a 时，如果前一位是 z ，那么就需要在前一位基础上继续往下算，即子串长度继续加 1；
3. 当当前位与前一位不连续时，这个时候子串长度应当从 1 开始重新计算

以 “zab” 为例进行说明：

1. 遍历 i=0 时，此时以 z 为结尾的连续子串只有 z ，因此统计个数为 1（z）；
2. 遍历 i=1 时，此时以 a 为结尾的连续子串为 za，因为是环形数组，所以 z 之后应该继续从 a 开始，此时统计个数为2（a，za）；
3. 遍历 i=2 时，此时以 b为结尾的连续子串为 zab，因此统计个数为3（b，ab，zab）；
4. 最后将三个字符对应的最长子串个数加起来等于 6 ，便是最终答案。

再以 “aabb” 为例说明存在重复字符时的处理过程：

1. 遍历 i=0 时，此时以 a 为结尾的连续子串只有 a ，因此统计个数为 1（a）；
2. 遍历 i=1 时，此时以 a 为结尾的连续子串为 a，此时子串个数为 1 ，但是因为前面出现过 a ，两个子串个数都是 1 ，因此以 a 为结尾的连续子串个数为 1（a）；
3. 遍历 i=2 时，此时以 b为结尾的连续子串为 ab，因此统计个数为2（b，ab）；
4. 遍历 i=3 时，此时以 b 为结尾的连续子串为 b，长度为 1（b），但是前面出现过一次 b，因此选择两个子串中个数较大的作为以 b 结尾的子串，最终结果为 2；
5. 遍历完成得到最终答案是 3。

代码中使用一 26 位的数组存放各个字符子串长度，count 统计子串长度，当不连续时，count 重置为 1，代码如下：

class Solution {    public int findSubstringInWraproundString(String p) { char[] chars = p.toCharArray(); int[] tmp = new int[26]; tmp[chars[0] - 'a'] = 1; int count = 1; for (int i = 1; i < chars.length; i++) {     if (chars[i] == chars[i - 1] + 1 || (chars[i] == 'a' && chars[i - 1] == 'z')) {  count++;     } else {  count = 1;     }     tmp[chars[i] - 'a'] = Math.max(count, tmp[chars[i] - 'a']); } int ans = 0; for (int i = 0; i < 26; i++) {     ans += tmp[i]; } return ans;    }}

2.2 测试结果

通过测试

3.总结

• 题目转换为求以字符结尾的连续子串长度更容易解答
• 使用 tmp 数组统计每一位字符为结尾的连续子数组个数
• 当存在不连续的时候，count 重置为 1
• 这道题其实挺难的，主要很容易陷入惯性思维，从头开始往后迭代进行字符判断，但是一旦把思维转换过来后所有问题都迎刃而解了