[LeetCode] 每日一题 3297. 统计重新排列后包含另一个字符串的子字符串数目 I

题目链接

https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i

题目描述

给你两个字符串 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 <= 105

• 1 <= word2.length <= 104

• word1 和 word2 都只包含小写英文字母。

题解

解题思路：

本题可以通过滑动窗口（Sliding Window）和字符频次比较的方式来解决。首先，我们定义合法子字符串为：如果一个子字符串的字符可以重新排列成 word2 的前缀，那么该子字符串是合法的。为了实现这一点，关键是判断一个窗口内的字符是否能通过排列组成 word2 的前缀

步骤如下：

1. 字符频次比较：

   • 对于每个合法的子字符串，字符的频次必须和 word2 的前缀字符频次完全一致。因此，问题可以转化为通过滑动窗口判断子字符串的字符频次是否等于 word2 前缀的字符频次

2. 滑动窗口：

   • 我们使用一个固定大小为 word2 长度的窗口，遍历 word1。在每个滑动窗口中，我们检查该窗口内字符的频次是否与 word2 前缀的频次相同

   • 为了高效比较窗口内字符频次是否符合要求，我们使用一个数组 diff 来维护当前窗口内与 word2 前缀字符频次的差异。当窗口内字符的差异为零时，表示当前窗口可以通过排列组成 word2 的前缀

3. 窗口扩展和收缩：

   • 通过滑动窗口的右端扩展来加入新的字符，并通过左端收缩来去除旧字符。在每次扩展和收缩后，更新 diff 数组，并根据 diffCount 来判断是否符合条件

4. 合法子字符串计数：

   • 当窗口内字符的差异为零时，说明当前窗口满足要求，此时从当前窗口的左边界到 word1 的结尾之间的所有子字符串都是合法的，因此可以加上 word1.length() - right + 1

代码实现

class Solution {
    public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return 0;
        }
        
        int len = word2.length();
        int[] diff = new int[26];
        
        // 初始化diff数组，记录word2的字符频次和word1的前len个字符频次的差异
        for (int i = 0; i < len; i++) {
            diff[word2.charAt(i) - 'a']++;
            diff[word1.charAt(i) - 'a']--;
        }

        // diffCount用来记录diff数组中大于零的数量，即当前窗口和word2的频次差异
        int diffCount = 0;
        for (int n : diff) {
            if (n > 0) {
                diffCount++;
            }
        }
        
        long ans = 0;
        int left = 0, right = len;

        // 滑动窗口处理
        while (left <= word1.length() - len) {
            // 右端扩展窗口
            while (right < word1.length() && diffCount > 0) {
                if (diff[word1.charAt(right) - 'a'] == 1) {
                    diffCount--;
                }
                diff[word1.charAt(right) - 'a']--;
                right++;
            }

            // 判断是否符合条件
            if (diffCount == 0) {
                ans += word1.length() - right + 1;
            }

            // 左端收缩窗口
            if (diff[word1.charAt(left) - 'a'] == 0) {
                diffCount++;
            }
            diff[word1.charAt(left) - 'a']++;
            left++;
        }

        return ans;
    }
}

复杂度分析

• 时间复杂度：

  • 滑动窗口的左右指针分别遍历 word1，时间复杂度为 O(m)，其中 m 是 word1 的长度

  • 在每次移动窗口时，更新 diff 数组和 diffCount 的操作是常数时间的 O(1)

  • 因此，整体时间复杂度为 O(m + n)，其中 m 是 word1 的长度，n 是 word2 的长度

• 空间复杂度：

  • 使用了一个固定大小的 diff 数组来记录每个字符的频次差异，空间复杂度为 O(26)，即 O(1)

总结

• 通过滑动窗口和字符频次差异的比较，能够有效地判断一个子字符串是否可以通过重新排列组成目标前缀

• 使用 diff 数组和 diffCount 来简化字符频次的更新和比较，避免了每次都进行全数组的遍历，提高了效率

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。