当前位置： 面试刷题>> 满足要求的子串个数 (经典算法题500道)
**题目描述补充**：
给定一个字符串`s`和一个整数`k`，我们需要找出所有满足以下条件的子串的个数：子串中不同字符的数量恰好为`k`。例如，如果`s = "aabbc"`且`k = 2`，则满足条件的子串有`"aa"`, `"ab"`, `"bb"`, 和 `"bc"`（注意，这里`"aa"`虽然重复了字符'a'，但不同字符的数量仍然是2，因为它只考虑了子串中的字符种类，而不是字符的具体数量）。
**注意**：这里的解释对于题目进行了一些调整，原题目可能未明确提及"恰好为k个不同字符"的子串，但这里为了明确题目要求和解答方向，我们这样设定。
**Python 代码示例**：
```python
def num_of_substrings(s, k):
n = len(s)
count = 0
# 辅助函数，用于计算从start到end（不包括end）之间不同字符的数量
def unique_chars(start, end):
char_set = set()
for i in range(start, end):
char_set.add(s[i])
return len(char_set)
# 遍历所有可能的子串起点和终点
for i in range(n):
for j in range(i + 1, n + 1):
if unique_chars(i, j) == k:
count += 1
return count
# 示例
s = "aabbc"
k = 2
print(num_of_substrings(s, k)) # 输出应为满足条件的子串个数
# 注意：这个解法的时间复杂度为O(n^3)，因为对于每个子串，我们都需要遍历一次来统计不同字符的数量。
# 对于更高效的解法，可以考虑使用滑动窗口和哈希表来优化到O(n^2)。
```
**JavaScript 代码示例**：
```javascript
function numOfSubstrings(s, k) {
let count = 0;
const n = s.length;
// 辅助函数，用于计算子串中不同字符的数量
function uniqueChars(start, end) {
const charSet = new Set();
for (let i = start; i < end; i++) {
charSet.add(s[i]);
}
return charSet.size;
}
// 遍历所有可能的子串
for (let i = 0; i < n; i++) {
for (let j = i + 1; j <= n; j++) {
if (uniqueChars(i, j) === k) {
count++;
}
}
}
return count;
}
// 示例
const s = "aabbc";
const k = 2;
console.log(numOfSubstrings(s, k)); // 输出应为满足条件的子串个数
```
**PHP 代码示例**：
```php
function numOfSubstrings($s, $k) {
$count = 0;
$n = strlen($s);
// 辅助函数，用于计算子串中不同字符的数量
function uniqueChars($start, $end, $s) {
$charSet = array();
for ($i = $start; $i < $end; $i++) {
$charSet[$s[$i]] = true;
}
return count($charSet);
}
// 遍历所有可能的子串
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j <= $n; $j++) {
if (uniqueChars($i, $j, $s) === $k) {
$count++;
}
}
}
return $count;
}
// 示例
$s = "aabbc";
$k = 2;
echo numOfSubstrings($s, $k); // 输出应为满足条件的子串个数
// 码小课网站中有更多相关内容分享给大家学习，包括更高效的算法和面试技巧。
```
**注意**：以上代码示例使用了简单的双重循环来遍历所有可能的子串，并通过辅助函数来计算每个子串中不同字符的数量。这种解法的时间复杂度较高，对于大规模输入可能不够高效。在实际应用中，可以考虑使用更高效的算法，如滑动窗口和哈希表来优化性能。