题目描述：

我们定义字符串 s 的 “环绕字符串” 是将字符串 s 中的字符按照顺序连接成一个圆形。例如，字符串 “abc” 的环绕字符串是 “abcabcabc…” 无限循环。

给定一个字符串 p，你需要找到 p 中不同环绕字符串的最小子串的数量。

示例：

输入: "a" 输出: 1

解释: 字符串列表 ["z", "a", "b", "za", "ab", "zab"].

解题思路：

1. 理解环绕字符串的特性：
   • 环绕字符串是无限循环的，所以我们只需要考虑字符串 p 中连续的子串。
   • 由于是环绕的，字符 'z' 后面可以接字符 'a'。
2. 动态规划的思想：
   • 我们可以用一个数组 count 来记录以每个字符结尾的最长连续子串的长度。
   • 例如，如果 p 中有子串 “abc”，那么 count['c'] 至少为 3。
3. 具体步骤：
   • 初始化一个长度为 26 的数组 count，用于记录每个字符结尾的最长连续子串长度。
   • 遍历字符串 p，记录当前连续子串的长度 length。
   • 如果当前字符和前一个字符是连续的（包括 'z' 到 'a' 的情况），则 length 增加 1，否则重置为 1。
   • 更新 count 数组：count[current_char] = max(count[current_char], length)。
   • 最后，count 数组中的所有元素之和即为答案。

代码实现：

class Solution: def findSubstringInWraproundString(self, p: str) -> int: if not p: return 0

    count = [0] * 26  # 用于记录以每个字符结尾的最长连续子串长度
    length = 0  # 当前连续子串的长度

    for i in range(len(p)):
        if i > 0 and (ord(p[i]) == ord(p[i - 1]) + 1 or (p[i] == 'a' and p[i - 1] == 'z')):
            length += 1
        else:
            length = 1
        count[ord(p[i]) - ord('a')] = max(count[ord(p[i]) - ord('a')], length)

    return sum(count)

sol = Solution() print(sol.findSubstringInWraproundString("a")) # 输出: 1 print(sol.findSubstringInWraproundString("cac")) # 输出: 2 print(sol.findSubstringInWraproundString("zab")) # 输出: 6

解释：

1. 初始化：
   • count 数组初始化为全 0，表示每个字符结尾的最长连续子串长度初始为 0。
   • length 初始为 0，表示当前连续子串的长度。
2. 遍历字符串 p：
   • 对于每个字符，检查它是否和前一个字符连续（包括 'z' 到 'a' 的情况）。
   • 如果连续，length 增加 1；否则，重置 length 为 1。
   • 更新 count 数组，确保记录的是最长连续子串的长度。
3. 计算结果：
   • 最后，count 数组中的所有元素之和即为不同环绕字符串的最小子串数量。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，因为 count 数组的长度是固定的 26。