大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

语文课代表来分析一下题意。

把 467. 环绕字符串中唯一的子字符串 - 图1个英文字母排列成一个圆圈 ⭕️，叫做 467. 环绕字符串中唯一的子字符串 - 图2。

另外给了一个字符串 467. 环绕字符串中唯一的子字符串 - 图3，让我们找出 467. 环绕字符串中唯一的子字符串 - 图4的所有子串中，在 467. 环绕字符串中唯一的子字符串 - 图5中的有多少个。

由于 467. 环绕字符串中唯一的子字符串 - 图6的子串可能会有重复的，因此重复的子串只算 467. 环绕字符串中唯一的子字符串 - 图7个。

注：子串与子序列的区别： 子串要求连续，子序列不需要连续。

解题方法

分析

遇到子串，一般会想到「滑动窗口」和「动态规划」。

本地的思想其实是「滑动窗口」和「动态规划」相结合。

子串相关的动态规划，一般状态的定义都是「以位置 467. 环绕字符串中唯一的子字符串 - 图8作为结尾的、符合要求的子串长度」。

这样定义，主要是为了简化，因为知道了 467. 环绕字符串中唯一的子字符串 - 图9以后，很容易就能得到 467. 环绕字符串中唯一的子字符串 - 图10。

比如对于本题，我们把状态定义为「467. 环绕字符串中唯一的子字符串 - 图11中，以位置 467. 环绕字符串中唯一的子字符串 - 图12作为结尾的、在 467. 环绕字符串中唯一的子字符串 - 图13中存在的最长子串长度」。

那么在已知了 467. 环绕字符串中唯一的子字符串 - 图14以后，得到 467. 环绕字符串中唯一的子字符串 - 图15时，无非两种情况：

  1. 当在 467. 环绕字符串中唯一的子字符串 - 图16中， 467. 环绕字符串中唯一的子字符串 - 图17是 467. 环绕字符串中唯一的子字符串 - 图18的下一个字符，那么说明能连接上，于是 $dp[i + 1] = dp[i] + 1$。
  2. 当在 467. 环绕字符串中唯一的子字符串 - 图19中， 467. 环绕字符串中唯一的子字符串 - 图20不是 467. 环绕字符串中唯一的子字符串 - 图21的下一个字符，那么说明能连接不上，于是 $dp[i + 1] = 1$。

看下面的动图，就明白了。

当出现重复的字符时，我们要取最大。

代码

使用一个字典保存以每个字符为结尾的最长字符串长度。

Python 代码如下：

  1. class Solution:
  2.     def findSubstringInWraproundString(self, p):
  3.         """
  4.         :type p: str
  5.         :rtype: int
  6.         """
  7.         count = collections.defaultdict(int)
  8.         N = len(p)
  9.         _len = 0
  10.         for i in range(N):
  11.             if i > 0 and (ord(p[i]) - ord(p[i - 1]) == 1 or (p[i] == 'a' and p[i - 1] == 'z')):
  12.                 _len += 1
  13.             else:
  14.                 _len = 1
  15.             count[p[i]] = max(count[p[i]], _len)
  16.         return sum(count.values())

复杂度

  • 时间复杂度：467. 环绕字符串中唯一的子字符串 - 图22，467. 环绕字符串中唯一的子字符串 - 图23是字符串长度。
  • 空间复杂度：467. 环绕字符串中唯一的子字符串 - 图24，只用了一个字典，字典的大小为 $26$。

总结

  1. 字符串结合动态规划的套路。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。