Medium

题目描述

给定一个字符串 s 和一个整数 k，返回 s 的子字符串总数，其中至少有一个字符出现至少 k 次。

示例 1：

输入：s = "abacb", k = 2
输出：4
解释：
有效的子字符串包括：
- "aba"（字符 'a' 出现 2 次）
- "abac"（字符 'a' 出现 2 次）
- "abacb"（字符 'a' 出现 2 次）
- "bacb"（字符 'b' 出现 2 次）

示例 2：

输入：s = "abcde", k = 1
输出：15
解释：
所有子字符串都有效，因为每个字符至少出现一次。

约束条件：

  • 1 <= s.length <= 3000
  • 1 <= k <= s.length
  • s 只包含小写英文字母

提示：

  • 固定子字符串的 left 索引
  • 对于固定的 left 索引，找到第一个使得子字符串 s[left..right] 满足条件的 right 索引
  • 所有从 left 开始且在 right 之后结束的子字符串都满足条件

解题思路

这道题要求找到所有至少包含一个字符出现频次不少于 k 次的子字符串。根据提示，我们可以采用固定左端点枚举右端点的策略。

核心思路：

  1. 对于每个左端点 left，我们逐步扩展右端点 right
  2. 在扩展过程中维护当前窗口内每个字符的频次
  3. 一旦发现有字符频次达到 k，那么从当前右端点到字符串末尾的所有右端点都能形成满足条件的子字符串

算法步骤：

  • 外层循环枚举左端点 left
  • 内层循环扩展右端点 right，同时更新字符频次
  • 当发现第一个字符频次达到 k 时，从当前位置到字符串末尾的所有子字符串都满足条件
  • 直接计算贡献并跳出内层循环

时间复杂度优化： 由于一旦找到满足条件的最小子字符串，后续更长的子字符串必然也满足条件，所以可以直接计算剩余长度的贡献，避免重复计算。

这种方法的时间复杂度为 O(n²)，空间复杂度为 O(1)（只需要常数大小的数组存储26个字母的频次）。

代码实现

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int n = s.length();
        int result = 0;
        
        for (int left = 0; left < n; left++) {
            vector<int> count(26, 0);
            
            for (int right = left; right < n; right++) {
                count[s[right] - 'a']++;
                
                // Check if any character has frequency >= k
                bool found = false;
                for (int i = 0; i < 26; i++) {
                    if (count[i] >= k) {
                        found = true;
                        break;
                    }
                }
                
                if (found) {
                    // All substrings from left to right, right+1, ..., n-1 are valid
                    result += n - right;
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        result = 0
        
        for left in range(n):
            count = [0] * 26
            
            for right in range(left, n):
                count[ord(s[right]) - ord('a')] += 1
                
                # Check if any character has frequency >= k
                if any(c >= k for c in count):
                    # All substrings from left to right, right+1, ..., n-1 are valid
                    result += n - right
                    break
        
        return result

public class Solution {
    public int NumberOfSubstrings(string s, int k) {
        int n = s.Length;
        int result = 0;
        
        for (int left = 0; left < n; left++) {
            int[] count = new int[26];
            
            for (int right = left; right < n; right++) {
                count[s[right] - 'a']++;
                
                // Check if any character has frequency >= k
                bool found = false;
                for (int i = 0; i < 26; i++) {
                    if (count[i] >= k) {
                        found = true;
                        break;
                    }
                }
                
                if (found) {
                    // All substrings from left to right, right+1, ..., n-1 are valid
                    result += n - right;
                    break;
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var numberOfSubstrings = function(s, k) {
    const n = s.length;
    let result = 0;
    
    for (let left = 0; left < n; left++) {
        const count = new Array(26).fill(0);
        
        for (let right = left; right < n; right++) {
            count[s.charCodeAt(right) - 97]++;
            
            // Check if any character has frequency >= k
            let found = false;
            for (let i = 0; i < 26; i++) {
                if (count[i] >= k) {
                    found = true;
                    break;
                }
            }
            
            if (found) {
                // All substrings from left to right, right+1, ..., n-1 are valid
                result += n - right;
                break;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²)
空间复杂度O(1)

详细分析：

  • 时间复杂度：外层循环 O(n)，内层循环最坏情况 O(n)，每次检查字符频次 O(26) = O(1)，总体 O(n²)
  • 空间复杂度：只需要长度为 26 的数组存储字符频次，为 O(1)