Leetcode 2953. Count Complete Substrings

• Leetcode 2953. Count Complete Substrings
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2953. Count Complete Substrings

1. 解题思路

这一题麻烦的点就在于说有两个限制条件，但是好的点在于说这两个限制条件事实上是相互独立的。

因此，我们可以通过第二个限制条件将字符串进行分段，此时目标子串必然在各个分段字符串之内，且此时我们只需要考虑第一个限制条件即可。

而对于第一个限制条件，一个简单的思路就是对26个字符建一个counter，然后分别对每一个位置作为起始点的情况进行考察。

显然，如果要成立，那么目标字符串长度一定是$k$的倍数，且如果任何一个字符的个数超过$k$时就一定不成立。

但是，直接这样的实现我们发现会出现超时，因此我们加了一些奇技淫巧用于优化算法，主要就是对于只有一个字符的情况进行了一下优化，因为如果只有一个字符的话，那么可能的个数就一定是$n-k+1$个。

2. 代码实现

给出python代码实现如下：

class Solution:def countCompleteSubstrings(self, word: str, k: int) -> int:def count_complete(s):n = len(s)if n < k:return 0if len(set(s)) == 1:return n-k+1cnt = [[0 for _ in range(26)] for _ in range(n+1)]for i, ch in enumerate(s):for j in range(26):cnt[i+1][j] = cnt[i][j]cnt[i+1][ord(ch) - ord('a')] += 1ans = 0for i in range(n-k+1):j = i+kwhile j <= n:diff = [y-x for x, y in zip(cnt[i], cnt[j])]if any(x > k for x in diff):breakif all(x == k or x == 0 for x in diff):ans += 1j += kreturn ansidx = 0i, n = 0, len(word)ans = 0while i < n-1:if abs(ord(word[i]) - ord(word[i+1])) > 2:ans += count_complete(word[idx:i+1])idx = i+1i += 1ans += count_complete(word[idx:])return ans

提交代码评测得到：耗时6583ms，占用内存582.8MB。