3298. 统计重新排列后包含另一个字符串的子字符串数目 II

题目链接：https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/

代码

/**
 * 3298. 统计重新排列后包含另一个字符串的子字符串数目 II
 * https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/
 */

function validSubstringCount(word1: string, word2: string): number {
    const arr1 = new Array(26).fill(0), arr2 = new Array(26).fill(0);
    let cnt = 0;
    let res = 0;
    let left = 0;
    for (const word of word2) {
        const index = word.charCodeAt(0) - 'a'.charCodeAt(0);
        arr2[index]++;
        if (arr2[index] === 1) {
            cnt++;
        }
    }
    for (let i = 0; i < word1.length; i++) {
        const index = word1[i].charCodeAt(0) - 'a'.charCodeAt(0);
        arr1[index]++;
        if (arr1[index] === arr2[index]) {
            cnt--;
        }
        while (cnt === 0) {
            const leftIndex = word1[left].charCodeAt(0) - 'a'.charCodeAt(0);
            if (arr1[leftIndex] === arr2[leftIndex]) {
                cnt++;
            }
            arr1[leftIndex]--;
            left++;
        }
        res += left;
    }
    return res;
}

思路

滑动窗口 + 计数数组统计字符数量：

1. 使用两个计数数组 arr1 和 arr2 分别记录窗口内和 word2 中每种字符的数量

2. 先统计 word2 中每种字符的数量，并记录需要满足的字符种类数 cnt

3. 对于每个右端点 i：

   • 将 word1[i] 加入窗口，更新计数
   • 当窗口内某个字符的数量达到 word2 中该字符的数量时，cnt 减 1
   • 当 cnt === 0 时（窗口包含 word2 的所有字符），收缩左边界 left，直到 cnt > 0
   • 此时 left 指向第一个不再满足条件的位置，以 i 为右端点的所有有效子字符串数量为 left（即 [0, i], [1, i], ..., [left-1, i] 共 left 个）

4. 累加所有右端点对应的子字符串数量

• 时间复杂度 $O(n+m)$，其中 $n$ 是 word1 的长度，$m$ 是 word2 的长度
• 空间复杂度 $O(1)$，计数数组固定大小为 26