统计完全子字符串

难度: Hard

给你一个字符串 word 和一个整数 k 。

如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：

s 中每个字符恰好出现 k 次。
相邻字符在字母表中的顺序至多相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差至多为 2 。

请你返回 word 中完全子字符串的数目。

子字符串 指的是一个字符串中一段连续非空的字符序列。

示例 1：

输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现 2 次，且相邻字符相差至多为 2 ：igigee, igigee, igigee 。

示例 2：

输入：word = "aaabbbccc", k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现 3 次，且相邻字符相差至多为 2 ：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。

提示：

1 <= word.length <= 10⁵
word 只包含小写英文字母。
1 <= k <= word.length

Submission

运行时间: 665 ms

内存: 21.3 MB

class Solution:
    def __init__(self):
        self.char_positions = [[] for _ in range(26)]  # 存储每个字符的出现位置
        self.word = ""
        self.k = 0

    def check(self, left):
        # 检查从left到right的子字符串是否满足每个字符恰好出现k次的条件
        new_left = left
        for i in range(26):
            if self.char_positions[i]:
                # 如果当前字符在[left, right]范围内出现
                if self.char_positions[i][-1] >= left:
                    # 如果当前字符出现次数不足k或超过k
                    n = len(self.char_positions[i])
                    if n < self.k:
                        return -1
                    if n > self.k:
                        if new_left <= self.char_positions[i][n - self.k - 1]:
                            return -1
                    new_left = min(new_left,self.char_positions[i][n - self.k])
        return new_left

    def countCompleteSubstrings(self, word, k):
        self.word = word
        self.k = k
        cut = 0  # 初始化切割点
        ans = 0  # 初始化答案
        for i in range(len(self.word)):
            char_index = ord(self.word[i]) - ord("a")  # 当前字符的索引
            self.char_positions[char_index].append(i)  # 更新字符位置

            # 如果相邻字符字母表顺序相差超过2，则更新切割点
            if i and abs(char_index - (ord(self.word[i - 1]) - ord("a"))) > 2:
                cut = i

            # 如果当前字符出现次数小于k，则继续
            if len(self.char_positions[char_index]) < self.k:
                continue

            pre = self.char_positions[char_index][
                len(self.char_positions[char_index]) - self.k
            ]
            while pre >= cut:
                new_pre = self.check(pre)
                if new_pre == -1:
                    break
                if new_pre == pre:
                    ans += 1
                    pre -= 1
                else:
                    pre = new_pre
        return ans

Explain

本题解采用了双指针法和哈希表来统计完全子字符串。首先，初始化一个长度为26的列表char_positions，用于存储每个字符在word中的出现位置。接着，遍历word中的每个字符，更新char_positions，并检查当前字符是否与前一个字符在字母表中的顺序相差超过2，如果是，则更新切割点cut。然后，检查当前字符出现的次数是否达到k次，如果达到，则调用check函数检查从pre（当前字符第k次出现的位置）到i（当前位置）的子字符串是否满足每个字符恰好出现k次的条件。如果满足，则增加答案计数器ans，并更新pre的位置，继续检查。最后，返回答案计数器ans。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def __init__(self):
        self.char_positions = [[] for _ in range(26)]  # 存储每个字符的出现位置
        self.word = \"\"
        self.k = 0

    def check(self, left):
        # 检查从left到right的子字符串是否满足每个字符恰好出现k次的条件
        new_left = left
        for i in range(26):
            if self.char_positions[i]:
                # 如果当前字符在[left, right]范围内出现
                if self.char_positions[i][-1] >= left:
                    # 如果当前字符出现次数不足k或超过k
                    n = len(self.char_positions[i])
                    if n < self.k:
                        return -1
                    if n > self.k:
                        if new_left <= self.char_positions[i][n - self.k - 1]:
                            return -1
                    new_left = min(new_left,self.char_positions[i][n - self.k])
        return new_left

    def countCompleteSubstrings(self, word, k):
        self.word = word
        self.k = k
        cut = 0  # 初始化切割点
        ans = 0  # 初始化答案
        for i in range(len(self.word)):
            char_index = ord(self.word[i]) - ord(\"a\")  # 当前字符的索引
            self.char_positions[char_index].append(i)  # 更新字符位置

            # 如果相邻字符字母表顺序相差超过2，则更新切割点
            if i and abs(char_index - (ord(self.word[i - 1]) - ord(\"a\"))) > 2:
                cut = i

            # 如果当前字符出现次数小于k，则继续
            if len(self.char_positions[char_index]) < self.k:
                continue

            pre = self.char_positions[char_index][
                len(self.char_positions[char_index]) - self.k
            ]
            while pre >= cut:
                new_pre = self.check(pre)
                if new_pre == -1:
                    break
                if new_pre == pre:
                    ans += 1
                    pre -= 1
                else:
                    pre = new_pre
        return ans

Explore

在`check`函数中，处理当前字符出现次数不足k或超过k的情况是为了确保每个字符在考虑的子字符串中正好出现k次。这是算法的核心要求之一，因为我们的目标是找到所有的完全子字符串，即每个字符都恰好出现k次的子字符串。如果某个字符出现次数不足k，则该子字符串显然不满足条件。如果出现次数超过k，我们需要进一步检查这些额外的出现是否影响子字符串的边界，即可能需要调整子字符串的起始位置。这些逻辑确保了每次计数时，子字符串严格符合完全子字符串的定义。

在相邻字符的字母表顺序相差超过2时更新切割点cut的目的是为了优化算法性能，并减少不必要的检查。这种更新基于一个观察：如果两个连续字符在字母表中的位置差距较大，这很可能意味着它们在字符串中不会形成一个频繁出现的模式，因此可以从新的位置开始考虑新的完全子字符串的开始。这样做可以避免在不可能形成完全子字符串的区间内进行不必要的检查，从而提高整体的算法效率。

在`countCompleteSubstrings`函数中，判断一个子字符串从pre到i是否每个字符恰好出现k次的判断是通过调用`check`函数实现的。具体步骤如下： 1. 从给定的起点pre开始，逐个检查26个字母的出现情况。 2. 对于每个字符，检查其在`char_positions`列表中记录的位置。如果该字符在考虑的范围内[left, right]出现次数不足k或超过k，则直接返回-1，表示该子字符串不满足条件。 3. 如果字符出现次数恰好为k，检查这些位置是否在当前考虑的子字符串范围内，并可能根据情况调整子字符串的起始位置new_left。 4. 如果所有字符都满足恰好出现k次的条件，最终返回调整后的起始位置new_left，这个位置即是验证通过的新的起始点。如果从任一位置开始的子字符串都不满足条件，则返回-1。