网站的备案的要多少钱,做网站 看什么书,小程序开发制作平台源码,建筑网站搜图【LetMeFly】3297.统计重新排列后包含另一个字符串的子字符串数目 I#xff1a;滑动窗口
力扣题目链接#xff1a;https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/
给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新…【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 1051 word2.length 104word1 和 word2 都只包含小写英文字母。
解题方法滑动窗口
首先统计word2中每个字符分别出现了多少次接着开始滑动窗口 窗口起点是word1的每个字符窗口终点是第一次“合法”的最小结束位置。 对于一个起点l若最小合法位置是r则合法方案是[l, r]、[l, r 1]、...、[l, len(word1) - 1]。
时间复杂度 O ( l e n ( w o r d 1 ) × C l e n ( w o r d 2 ) ) O(len(word1)\times Clen(word2)) O(len(word1)×Clen(word2))其中 C 26 C26 C26空间复杂度 O ( C ) O(C) 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
abc1
*/
/*
abcabc
abc10
*/
int main() {Solution sol;string a, b;while (cin a b) {cout sol.validSubstringCount(a, b) endl;}return 0;
}
#endifPython Author: LetMeFly
Date: 2025-01-09 12:39:58
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-09 12:44:30from collections import Counter, defaultdictclass Solution:def ok(self, cnt1: defaultdict) - bool:for k, v in self.cnt2.items():if cnt1[k] v:return Falsereturn Truedef validSubstringCount(self, word1: str, word2: str) - int:self.cnt2 Counter(word2)cnt1 defaultdict(int)ans l r 0while l len(word1):if l:cnt1[word1[l - 1]] - 1while not self.ok(cnt1):if r len(word1):return anscnt1[word1[r]] 1r 1ans len(word1) - r 1l 1return 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 fmtfunc 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
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/145031494
