给定一个字符串 S 。S 仅包含小写英文字母。(10≤length(S)≤1,000,000) 有多少子串包含至少 k(1≤k≤26) 个不同的字符？

```python def count_substrings(S, k): n = len(S) count = 0 # 遍历所有可能的子串起始位置 for i in range(n): # 用于记录当前子串中不同字符的集合 unique_chars = set() # 遍历所有可能的子串结束位置 for j in range(i, n): # 将当前字符加入集合 unique_chars.add(S[j]) # 如果集合中不同字符的数量大于等于 k if len(unique_chars) >= k: # 找到满足条件的子串，计数加 1 count = count + 1 return count # 示例使用 S = "abcabc" k = 2 print(count_substrings(S, k)) ``` 额外注意逻辑点 1. 双重循环的时间复杂度是 $O(n^2)$，对于较长的字符串，可能会导致性能问题。在实际应用中，如果字符串长度非常大，需要考虑更高效的算法。 2. 在每次内层循环中，集合的添加操作虽然平均时间复杂度是 $O(1)$，但在极端情况下可能会有性能波动，需要注意。 3. 代码中没有对输入的字符串长度和 `k` 的范围进行检查，在实际使用时，建议添加输入验证逻辑，确保输入符合题目要求。 [2025-07-23 11:41:41 | AI写代码神器 | 313点数解答]