当前位置：首页 > article >正文

LeetCode 3297.统计重新排列后包含另一个字符串的子字符串数目 I：滑动窗口

article 2025/3/1 19:14:29

【LetMeFly】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 <= 10⁵
1 <= word2.length <= 10⁴
word1 和 word2 都只包含小写英文字母。

解题方法：滑动窗口

首先统计word2中每个字符分别出现了多少次，接着开始滑动窗口：

窗口起点是word1的每个字符，窗口终点是第一次“合法”的最小结束位置。

对于一个起点l，若最小合法位置是r，则合法方案是[l, r]、[l, r + 1]、...、[l, len(word1) - 1]。

时间复杂度 $O(len(word1)\times C+len(word2))$ ，其中 $C = 26$
空间复杂度 $O (C)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-01-09 11:03:16
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-09 12:39:10
 */
typedef long long ll;
class Solution {
private:
    bool ok(int* cnt1, int* cnt2) {
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return false;
            }
        }
        return true;
    }
public:
    ll validSubstringCount(string& word1, string& word2) {
        int cnt1[26] = {0}, cnt2[26] = {0};
        for (char c : word2) {
            cnt2[c - 'a']++;
        }
        ll ans = 0;
        for (int l = 0, r = 0; l < word1.size(); l++, r = max(r, l)) {
            if (l) {
                cnt1[word1[l - 1] - 'a']--;
            }
            while (!ok(cnt1, cnt2)) {
                if (r == word1.size()) {
                    return ans;
                }
                cnt1[word1[r++] - 'a']++;
            }
            ans += word1.size() - r + 1;
        }
        return ans;
    }
};

#ifdef _WIN32
/*
bcca
abc

1
*/
/*
abcabc
abc

10
*/
int main() {
    Solution sol;
    string a, b;
    while (cin >> a >> b) {
        cout << sol.validSubstringCount(a, b) << endl;
    }
    return 0;
}
#endif

Python

'''
Author: LetMeFly
Date: 2025-01-09 12:39:58
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-09 12:44:30
'''
from collections import Counter, defaultdict


class Solution:
    def ok(self, cnt1: defaultdict) -> bool:
        for k, v in self.cnt2.items():
            if cnt1[k] < v:
                return False
        return True
    
    def validSubstringCount(self, word1: str, word2: str) -> int:
        self.cnt2 = Counter(word2)
        cnt1 = defaultdict(int)
        ans = l = r = 0
        while l < len(word1):
            if l:
                cnt1[word1[l - 1]] -= 1
            while not self.ok(cnt1):
                if r == len(word1):
                    return ans
                cnt1[word1[r]] += 1
                r += 1
            ans += len(word1) - r + 1
            l += 1
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-01-09 12:46:14
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-09 12:51:13
 */
class Solution {
    private boolean ok(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] < b[i]) {
                return false;
            }
        }
        return true;
    }

    public long validSubstringCount(String word1, String word2) {
        int[] cnt1 = new int[26], cnt2 = new int[26];
        for (char c : word2.toCharArray()) {
            cnt2[c - 'a']++;
        }
        long ans = 0;
        for (int l = 0, r = 0; l < word1.length(); l++) {
            if (l > 0) {
                cnt1[word1.charAt(l - 1) - 'a']--;
            }
            while (!ok(cnt1, cnt2)) {
                if (r == word1.length()) {
                    return ans;
                }
                cnt1[word1.charAt(r++) - 'a']++;
            }
            ans += word1.length() - r + 1;
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-01-09 12:52:14
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-09 13:10:20
 */
package main

// import "fmt"

func ok(a, b []int) bool {
    for i := range a {
        if a[i] < b[i] {
            return false
        }
    }
    return true
}

func validSubstringCount(word1 string, word2 string) (ans int64) {
    cnt1, cnt2 := make([]int, 26), make([]int, 26)
    for _, c := range word2 {
        cnt2[c - 'a']++
    }
    // fmt.Println(cnt2)
    for l, r := 0, 0; l < len(word1); l++ {
        if l > 0 {
            cnt1[word1[l - 1] - 'a']--
        }
        for !ok(cnt1, cnt2) {
            if r == len(word1) {
                return
            }
            cnt1[word1[r] - 'a']++
            r++
        }
        // fmt.Println(cnt1)
        // fmt.Println(r)
        ans += int64(len(word1) - r + 1)
    }
    return
}