日期: 2025 年 1 月 9 日

目标

给你两个字符串 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 <= 10^5
• 1 <= word2.length <= 10^4
• word1 和 word2 都只包含小写英文字母。

思路

有两个字符串 word1 和 word2，求 word1 有多个子字符串 满足子串的每个字符的出现次数 均大于等于 word2 中对应字符的出现次数。

暴力解法是枚举 word1 的每个子字符串，比较子串中的每个字符个数。具体来说就是统计 word1 与 word2 中各字符的个数，枚举 word1 起点，从后向前枚举终点，如果某字符个数小于 word2 相应字符的个数则停止计数，继续下一个起点。这种解法的时间复杂度是 O(n^2) 会超时。

考虑使用滑动窗口，当左边元素移出窗口时，向右扩展，直到移出的元素个数达到 word2 中对应字符的个数，累加右边界到结尾的字符个数。

代码

/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能