Leetcode 3298. Count Substrings That Can Be Rearranged to Contain a String II
- Leetcode 3298. Count Substrings That Can Be Rearranged to Contain a String II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3298. Count Substrings That Can Be Rearranged to Contain a String II
1. 解题思路
这一题和题目3297本质上就是一道题目，然后就是要优化一下算法，使之可以在 O ( N ) O(N) O(N)的时间复杂度内完成。
整体思路的话其实还是非常简单的，就是一个滑动窗口的思路，我们考察每一个位置作为左边界 i i i时，右边界的临界位置 j j j的坐标，此时能够给到的总的substring的个数就是 n − j + 1 n-j+1 n−j+1个。
因此，对于题目3297，我们可以快速的给出一个非常直接地实现如下：
class Solution:def validSubstringCount(self, word1: str, word2: str) -> int:i, j, n = 0, 0, len(word1)cnt2 = Counter(word2)cnt = defaultdict(int)ans = 0while i < n:while j < n and any(cnt[ch] < cnt2[ch] for ch in string.ascii_lowercase):cnt[word1[j]] += 1j += 1if all(cnt[ch] >= cnt2[ch] for ch in string.ascii_lowercase):ans += n-j+1cnt[word1[i]] -= 1i += 1else:breakreturn ans
这个算法其实已经是一个 O ( N ) O(N) O(N)时间复杂度的算法了，不过对于题目3298，他还是没法通过全部的测试样例，因此，我们在这里就需要对这段代码进行一下优化，主要包括三个点的优化：
- 将counter的存储形式从dict修改为list，因为array的坐标查找比hash更快；
- 对于word2当中的字符，我们不需要遍历全部的26个字符，只需要查找word2当中出现过的字符即可，这样的话也可以有一定的效率优化；
- 当j固定之后，对于i的判断，我们不需要一直判断26个字母，只需要判断当前滑动删除的字符在删除前后是否还满足不少于word2即可。
然后，经过修改的代码就可以通过全部的测试样例了。
2. 代码实现
给出最终的python代码实现如下：
class Solution:def validSubstringCount(self, word1: str, word2: str) -> int:a = ord('a')i, j, n = 0, 0, len(word1)cnt2 = [0 for _ in range(26)]for ch in word2:cnt2[ord(ch) - a] += 1valids = [i for i in range(26) if cnt2[i] > 0]cnt = [0 for _ in range(26)]ans = 0while i < n:while j < n and any(cnt[i] < cnt2[i] for i in valids):cnt[ord(word1[j]) - a] += 1j += 1if j < n:ans += n-j+1cnt[ord(word1[i]) - a] -= 1i += 1else:breakif all(cnt[i] >= cnt2[i] for i in valids):while i < n and cnt[ord(word1[i]) - a] >= cnt2[ord(word1[i]) - a]:ans += n-j+1cnt[ord(word1[i]) - a] -= 1if cnt[ord(word1[i]) - a] < cnt2[ord(word1[i]) - a]:breaki += 1return ans
提交代码评测得到：耗时11046ms，占用内存26.3MB。