LeetCode：3298. 统计重新排列后包含另一个字符串的子字符串数目 II（滑动窗口 Java）

目录

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

题目描述：

实现代码与解析：

滑动窗口

原理思路：

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

题目描述：

        给你两个字符串 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 都只包含小写英文字母。

实现代码与解析：

滑动窗口

class Solution {
    public long validSubstringCount(String word1, String word2) {
 
        if (word1.length() < word2.length()) {
            return 0;
        }
 
        int[] hash = new int[26];
        // 种类
        int cnt = 0;
        for (char c : word2.toCharArray()) {
            if (hash[c - 'a']++ == 0) cnt++;
        }
 
        int[] cur = new int[26];
 
        long res = 0;
        for (int l = 0, r = 0; r < word1.length(); r++) {
 
            if (++cur[word1.charAt(r) - 'a'] == hash[word1.charAt(r) - 'a']) {
                cnt--;
            }
            while (cnt == 0) {
                if (cur[word1.charAt(l) - 'a'] == hash[word1.charAt(l) - 'a']) {
                    cnt++;
                }
                cur[word1.charAt(l) - 'a']--;
                l++;
            }
            res += l;
 
        }
        return res;
    }
}

原理思路：

        与昨日同。LeetCode：3297. 统计重新排列后包含另一个字符串的子字符串数目 I（滑动窗口 Java）-CSDN博客