2953. 统计完全子字符串的数量

Hard

题目描述

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

如果字符串 s 的一个子字符串满足以下条件，则称其为完全子字符串：

s 中每个字符都恰好出现 k 次。
相邻字符的差值不超过 2。也就是说，对于 s 中任意两个相邻字符 c1 和 c2，它们在字母表中位置的绝对差值不超过 2。

返回 word 中完全子字符串的数量。

子字符串是字符串中非空的连续字符序列。

示例 1：

输入：word = "igigee", k = 2
输出：3
解释：完全子字符串需要满足每个字符恰好出现两次，且相邻字符差值不超过 2 的条件：igigee, igigee, igigee。

示例 2：

输入：word = "aaabbbccc", k = 3
输出：6
解释：完全子字符串需要满足每个字符恰好出现三次，且相邻字符差值不超过 2 的条件：aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc。

提示：

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

解题思路

这道题需要找出满足两个条件的子字符串：每个字符恰好出现k次，且相邻字符差值不超过2。

核心思路是枚举所有可能的完全子字符串长度，然后使用滑动窗口来检查每个窗口是否满足条件。

分析关键点：

完全子字符串的长度必须是k的倍数，且最多有26种长度（k×1到k×26）
对于每种长度，使用固定大小的滑动窗口遍历字符串
需要同时维护两个条件：字符频次和相邻字符差值

算法步骤：

枚举窗口大小：从k到26×k（因为最多26个不同字母）
对每个窗口大小，使用滑动窗口遍历字符串
维护字符频次数组，检查是否所有字符都恰好出现k次
维护相邻字符差值的最大值，使用multiset动态维护
当窗口满足两个条件时，计数器加1

时间复杂度优化关键是使用multiset来动态维护相邻字符差值的最大值，避免每次都重新计算整个窗口。

代码实现

class Solution {
public:
    int countCompleteSubstrings(string word, int k) {
        int n = word.length();
        int result = 0;
        
        // 枚举窗口大小：k个字符到26*k个字符
        for (int windowSize = k; windowSize <= 26 * k && windowSize <= n; windowSize += k) {
            vector<int> freq(26, 0);
            multiset<int> diffs;
            
            // 初始化第一个窗口
            for (int i = 0; i < windowSize; i++) {
                freq[word[i] - 'a']++;
                if (i > 0) {
                    diffs.insert(abs(word[i] - word[i-1]));
                }
            }
            
            // 检查第一个窗口
            if (isValidWindow(freq, diffs, windowSize / k, k)) {
                result++;
            }
            
            // 滑动窗口
            for (int i = windowSize; i < n; i++) {
                // 移除左边字符
                int leftChar = word[i - windowSize] - 'a';
                freq[leftChar]--;
                if (i - windowSize > 0) {
                    diffs.erase(diffs.find(abs(word[i - windowSize] - word[i - windowSize - 1])));
                }
                
                // 添加右边字符
                int rightChar = word[i] - 'a';
                freq[rightChar]++;
                if (i > 0) {
                    diffs.insert(abs(word[i] - word[i-1]));
                }
                
                // 检查当前窗口
                if (isValidWindow(freq, diffs, windowSize / k, k)) {
                    result++;
                }
            }
        }
        
        return result;
    }
    
private:
    bool isValidWindow(const vector<int>& freq, const multiset<int>& diffs, int uniqueChars, int k) {
        // 检查相邻字符差值条件
        if (!diffs.empty() && *diffs.rbegin() > 2) {
            return false;
        }
        
        // 检查字符频次条件
        int validChars = 0;
        for (int f : freq) {
            if (f == k) validChars++;
            else if (f > 0) return false;
        }
        
        return validChars == uniqueChars;
    }
};

class Solution:
    def countCompleteSubstrings(self, word: str, k: int) -> int:
        from collections import defaultdict, Counter
        import bisect
        
        n = len(word)
        result = 0
        
        # 枚举窗口大小：k个字符到26*k个字符
        window_size = k
        while window_size <= 26 * k and window_size <= n:
            freq = defaultdict(int)
            diffs = []
            
            # 初始化第一个窗口
            for i in range(window_size):
                freq[word[i]] += 1
                if i > 0:
                    bisect.insort(diffs, abs(ord(word[i]) - ord(word[i-1])))
            
            # 检查第一个窗口
            if self.is_valid_window(freq, diffs, window_size // k, k):
                result += 1
            
            # 滑动窗口
            for i in range(window_size, n):
                # 移除左边字符
                left_char = word[i - window_size]
                freq[left_char] -= 1
                if freq[left_char] == 0:
                    del freq[left_char]
                if i - window_size > 0:
                    diff_to_remove = abs(ord(word[i - window_size]) - ord(word[i - window_size - 1]))
                    diffs.remove(diff_to_remove)
                
                # 添加右边字符
                right_char = word[i]
                freq[right_char] += 1
                if i > 0:
                    bisect.insort(diffs, abs(ord(word[i]) - ord(word[i-1])))
                
                # 检查当前窗口
                if self.is_valid_window(freq, diffs, window_size // k, k):
                    result += 1
            
            window_size += k
        
        return result
    
    def is_valid_window(self, freq, diffs, unique_chars, k):
        # 检查相邻字符差值条件
        if diffs and diffs[-1] > 2:
            return False
        
        # 检查字符频次条件
        valid_chars = sum(1 for f in freq.values() if f == k)
        invalid_chars = sum(1 for f in freq.values() if f != k)
        
        return valid_chars == unique_chars and invalid_chars == 0

public class Solution {
    public int CountCompleteSubstrings(string word, int k) {
        int n = word.Length;
        int result = 0;
        
        // 枚举窗口大小：k个字符到26*k个字符
        for (int windowSize = k; windowSize <= 26 * k && windowSize <= n; windowSize += k) {
            int[] freq = new int[26];
            var diffs = new SortedDictionary<int, int>();
            
            // 初始化第一个窗口
            for (int i = 0; i < windowSize; i++) {
                freq[word[i] - 'a']++;
                if (i > 0) {
                    int diff = Math.Abs(word[i] - word[i-1]);
                    if (diffs.ContainsKey(diff)) {
                        diffs[diff]++;
                    } else {
                        diffs[diff] = 1;
                    }
                }
            }
            
            // 检查第一个窗口
            if (IsValidWindow(freq, diffs, windowSize / k, k)) {
                result++;
            }
            
            // 滑动窗口
            for (int i = windowSize; i < n; i++) {
                // 移除左边字符
                int leftChar = word[i - windowSize] - 'a';
                freq[leftChar]--;
                if (i - windowSize > 0) {
                    int diffToRemove = Math.Abs(word[i - windowSize] - word[i - windowSize - 1]);
                    diffs[diffToRemove]--;
                    if (diffs[diffToRemove] == 0) {
                        diffs.Remove(diffToRemove);
                    }
                }
                
                // 添加右边字符
                int rightChar = word[i] - 'a';
                freq[rightChar]++;
                if (i > 0) {
                    int diff = Math.Abs(word[i] - word[i-1]);
                    if (diffs.ContainsKey(diff)) {
                        diffs[diff]++;
                    } else {
                        diffs[diff] = 1;
                    }
                }
                
                // 检查当前窗口
                if (IsValidWindow(freq, diffs, windowSize / k, k)) {
                    result++;
                }
            }
        }
        
        return result;
    }
    
    private bool IsValidWindow(int[] freq, SortedDictionary<int, int> diffs, int uniqueChars, int k) {
        // 检查相邻字符差值条件
        if (diffs.Count > 0 && diffs.Keys.Max() > 2) {
            return false;
        }
        
        // 检查字符频次条件
        int validChars = 0;
        foreach (int f in freq) {
            if (f == k) validChars++;
            else if (f > 0) return false;
        }
        
        return validChars == uniqueChars;
    }
}

var countCompleteSubstrings = function(word, k) {
    let result = 0;
    
    // Split word into segments where adjacent chars differ by at most 2
    let segments = [];
    let start = 0;
    
    for (let i = 1; i < word.length; i++) {
        if (Math.abs(word.charCodeAt(i) - word.charCodeAt(i-1)) > 2) {
            segments.push(word.slice(start, i));
            start = i;
        }
    }
    segments.push(word.slice(start));
    
    // For each segment, count complete substrings
    for (let segment of segments) {
        result += countCompleteInSegment(segment, k);
    }
    
    return result;
};

function countCompleteInSegment(s, k) {
    let count = 0;
    let n = s.length;
    
    // Try all possible numbers of unique characters (1 to 26)
    for (let uniqueChars = 1; uniqueChars <= 26 && uniqueChars * k <= n; uniqueChars++) {
        let windowSize = uniqueChars * k;
        let charCount = new Map();
        let validChars = 0;
        
        // Initialize first window
        for (let i = 0; i < windowSize; i++) {
            let char = s[i];
            charCount.set(char, (charCount.get(char) || 0) + 1);
            if (charCount.get(char) === k) {
                validChars++;
            } else if (charCount.get(char) === k + 1) {
                validChars--;
            }
        }
        
        if (validChars === uniqueChars) {
            count++;
        }
        
        // Slide window
        for (let i = windowSize; i < n; i++) {
            // Remove leftmost character
            let leftChar = s[i - windowSize];
            if (charCount.get(leftChar) === k) {
                validChars--;
            } else if (charCount.get(leftChar) === k + 1) {
                validChars++;
            }
            charCount.set(leftChar, charCount.get(leftChar) - 1);
            
            // Add rightmost character
            let rightChar = s[i];
            charCount.set(rightChar, (charCount.get(rightChar) || 0) + 1);
            if (charCount.get(rightChar) === k) {
                validChars++;
            } else if (charCount.get(rightChar) === k + 1) {
                validChars--;
            }
            
            if (validChars === uniqueChars) {
                count++;
            }
        }
    }
    
    return count;
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小
时间复杂度	O(26 × n × log(n))
空间复杂度	O(n)

时间复杂度分析：外层循环最多26次（不同的窗口大小），内层滑动窗口遍历n个位置，每次操作multiset需要O(log n)时间。

空间复杂度分析：需要O(26)的频次数组和O(n)的差值multiset存储空间。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目