跳转至

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

来源第 416 场周赛 Q4难度困难分数1909

题目描述

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。

 

示例 1：

输入：word1 = "bcca", word2 = "abc"

输出：1

解释：

唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"

输出：10

解释：

除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"

输出：0

 

解释：

  • 1 <= word1.length <= 106
  • 1 <= word2.length <= 104
  • word1 和 word2 都只包含小写英文字母。

解法

方法一：滑动窗口

思考

题意与 I 相同，仅数据范围更大，必须沿用线性滑窗而不能枚举子串。覆盖仍由「每种字符数量不少于 \(\textit{word2}\)」刻画，单调性不变。

同一套 \(need\) 与窗口计数：右端纳入、左端在仍覆盖时右移，答案累加当前左端。长度不足时直接 \(0\)。总时间线性。

题目实际上是求在 \(\textit{word1}\) 中，有多少个子串包含了 \(\textit{word2}\) 中的所有字符。我们可以使用滑动窗口来处理。

首先，如果 \(\textit{word1}\) 的长度小于 \(\textit{word2}\) 的长度，那么 \(\textit{word1}\) 中不可能包含 \(\textit{word2}\) 的所有字符，直接返回 \(0\)。

接下来，我们用一个哈希表或长度为 \(26\) 的数组 \(\textit{cnt}\) 来统计 \(\textit{word2}\) 中的字符出现的次数。然后，我们用 \(\textit{need}\) 来记录还需要多少个字符才能满足条件，初始化为 \(\textit{cnt}\) 的长度。

接着，我们用一个滑动窗口 \(\textit{win}\) 来记录当前窗口中的字符出现的次数。我们用 \(\textit{ans}\) 来记录满足条件的子串的个数，用 \(\textit{l}\) 来记录窗口的左边界。

遍历 \(\textit{word1}\) 中的每个字符，对于当前字符 \(c\)，我们将其加入到 \(\textit{win}\) 中，如果 \(\textit{win}[c]\) 的值等于 \(\textit{cnt}[c]\)，那么说明当前窗口中已经包含了 \(\textit{word2}\) 中的所有字符之一，那么 \(\textit{need}\) 减一。如果 \(\textit{need}\) 等于 \(0\)，说明当前窗口中包含了 \(\textit{word2}\) 中的所有字符，我们需要缩小窗口的左边界，直到 \(\textit{need}\) 大于 \(0\)。具体地，如果 \(\textit{win}[\textit{word1}[l]]\) 等于 \(\textit{cnt}[\textit{word1}[l]]\)，那么说明当前窗口中包含了 \(\textit{word2}\) 中的所有字符之一，那么缩小窗口的左边界之后，就不满足条件了，所以 \(\textit{need}\) 加一，同时 \(\textit{win}[\textit{word1}[l]]\) 减一。然后，我们将 \(\textit{l}\) 加一。此时窗口为 \([l, r]\)，那么对于任意 \(0 \leq l' \lt l\)，\([l', r]\) 都是满足条件的子串，一共有 \(l\) 个，我们累加到答案中。

遍历完 \(\textit{word1}\) 中的所有字符之后，我们就得到了答案。

时间复杂度 \(O(n + m)\)，其中 \(n\) 和 \(m\) 分别是 \(\textit{word1}\) 和 \(\textit{word2}\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集，这里是小写字母集合，所以空间复杂度是常数级别的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word1) < len(word2):
            return 0
        cnt = Counter(word2)
        need = len(cnt)
        ans = l = 0
        win = Counter()
        for c in word1:
            win[c] += 1
            if win[c] == cnt[c]:
                need -= 1
            while need == 0:
                if win[word1[l]] == cnt[word1[l]]:
                    need += 1
                win[word1[l]] -= 1
                l += 1
            ans += l
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return 0;
        }
        int[] cnt = new int[26];
        int need = 0;
        for (int i = 0; i < word2.length(); ++i) {
            if (++cnt[word2.charAt(i) - 'a'] == 1) {
                ++need;
            }
        }
        long ans = 0;
        int[] win = new int[26];
        for (int l = 0, r = 0; r < word1.length(); ++r) {
            int c = word1.charAt(r) - 'a';
            if (++win[c] == cnt[c]) {
                --need;
            }
            while (need == 0) {
                c = word1.charAt(l) - 'a';
                if (win[c] == cnt[c]) {
                    ++need;
                }
                --win[c];
                ++l;
            }
            ans += l;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        if (word1.size() < word2.size()) {
            return 0;
        }
        int cnt[26]{};
        int need = 0;
        for (char& c : word2) {
            if (++cnt[c - 'a'] == 1) {
                ++need;
            }
        }
        long long ans = 0;
        int win[26]{};
        int l = 0;
        for (char& c : word1) {
            int i = c - 'a';
            if (++win[i] == cnt[i]) {
                --need;
            }
            while (need == 0) {
                i = word1[l] - 'a';
                if (win[i] == cnt[i]) {
                    ++need;
                }
                --win[i];
                ++l;
            }
            ans += l;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func validSubstringCount(word1 string, word2 string) (ans int64) {
    if len(word1) < len(word2) {
        return 0
    }
    cnt := [26]int{}
    need := 0
    for _, c := range word2 {
        cnt[c-'a']++
        if cnt[c-'a'] == 1 {
            need++
        }
    }
    win := [26]int{}
    l := 0
    for _, c := range word1 {
        i := int(c - 'a')
        win[i]++
        if win[i] == cnt[i] {
            need--
        }
        for need == 0 {
            i = int(word1[l] - 'a')
            if win[i] == cnt[i] {
                need++
            }
            win[i]--
            l++
        }
        ans += int64(l)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function validSubstringCount(word1: string, word2: string): number {
    if (word1.length < word2.length) {
        return 0;
    }
    const cnt: number[] = Array(26).fill(0);
    let need: number = 0;
    for (const c of word2) {
        if (++cnt[c.charCodeAt(0) - 97] === 1) {
            ++need;
        }
    }
    const win: number[] = Array(26).fill(0);
    let [ans, l] = [0, 0];
    for (const c of word1) {
        const i = c.charCodeAt(0) - 97;
        if (++win[i] === cnt[i]) {
            --need;
        }
        while (need === 0) {
            const j = word1[l].charCodeAt(0) - 97;
            if (win[j] === cnt[j]) {
                ++need;
            }
            --win[j];
            ++l;
        }
        ans += l;
    }
    return ans;
}

评论