求含恰好k个不同字符的子串数量的滑动窗口解法疑问

核心需求 #

统计字符串中恰好包含k个不同字符的子串总数，子串允许重复字符，仅要求不同字符的数量严格等于k。

原思路的问题 #

你提到的“当计数等于k时将答案加1，随后终止循环重启滑动窗口”的做法会遗漏大量符合条件的子串。比如字符串"abac"，k=2，当窗口扩展到"ab"时符合条件，但继续扩展到"aba"（不同字符还是a、b）也符合条件，直接重启窗口会漏掉这类情况。

正确的滑动窗口实现思路 #

我们可以通过统计最多包含k个不同字符的子串数减去最多包含k-1个不同字符的子串数，得到恰好包含k个不同字符的子串数，这种方式更高效且不易遗漏：

• 实现一个辅助函数countAtMostK(s, k)，计算字符串s中最多包含k个不同字符的子串总数：
  • 用哈希表charCount记录窗口内每个字符的出现次数
  • 初始化左指针left=0，结果res=0
  • 遍历右指针right，对每个字符s[right]：
    • 如果charCount[s[right]]为0，说明是新字符，将k减1
    • 递增charCount[s[right]]的计数
    • 当k<0时，需要收缩左指针：递减s[left]的计数，如果计数变为0，将k加1，然后左指针右移
    • 每次循环，当前窗口内的子串数为right - left + 1，累加到res中
• 最终结果就是countAtMostK(s, k) - countAtMostK(s, k-1)

代码示例（Python） #

def countKDistinctSubstrings(s, k):
    def countAtMostK(s, k):
        char_count = {}
        left = 0
        res = 0
        for right in range(len(s)):
            char = s[right]
            if char not in char_count or char_count[char] == 0:
                k -= 1
            char_count[char] = char_count.get(char, 0) + 1
            
            while k < 0:
                left_char = s[left]
                char_count[left_char] -= 1
                if char_count[left_char] == 0:
                    k += 1
                left += 1
            
            res += right - left + 1
        return res
    
    return countAtMostK(s, k) - countAtMostK(s, k-1)

为什么这种方式可行？ #

• 最多包含k个不同字符的子串数，包含了所有恰好1、2、...、k个不同字符的子串
• 最多包含k-1个不同字符的子串数，包含了所有恰好1、2、...、k-1个不同字符的子串
• 两者相减，就得到了恰好包含k个不同字符的子串数，完美覆盖所有情况

内容的提问来源于stack exchange，提问作者Udit Raj Vashisth