当前位置: 面试刷题>> 满足要求的子串个数 (经典算法题500道)


题目描述补充

给定一个字符串s和一个整数k,我们需要找出所有满足以下条件的子串的个数:子串中不同字符的数量恰好为k。例如,如果s = "aabbc"k = 2,则满足条件的子串有"aa", "ab", "bb", 和 "bc"(注意,这里"aa"虽然重复了字符'a',但不同字符的数量仍然是2,因为它只考虑了子串中的字符种类,而不是字符的具体数量)。

注意:这里的解释对于题目进行了一些调整,原题目可能未明确提及"恰好为k个不同字符"的子串,但这里为了明确题目要求和解答方向,我们这样设定。

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 代码示例

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 代码示例

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);  // 输出应为满足条件的子串个数

// 码小课网站中有更多相关内容分享给大家学习,包括更高效的算法和面试技巧。

注意:以上代码示例使用了简单的双重循环来遍历所有可能的子串,并通过辅助函数来计算每个子串中不同字符的数量。这种解法的时间复杂度较高,对于大规模输入可能不够高效。在实际应用中,可以考虑使用更高效的算法,如滑动窗口和哈希表来优化性能。

推荐面试题