Readme

3298.Count-Substrings-That-Can-Be-Rearranged-to-Contain-a-String-II

解法1

本题就是问有多少个子区间，里面包含了word2的所有字符。

假设固定了一个滑窗的左端点i，我们试图寻找符合条件的右端点j。不难发现，只需要单调增加j就可以找到一个最短的区间，之后右端点从j到n-1变化都是可以的，故总计数增加n-j. 然后我们思考当左端点变成i+1时，我们相比之前减少了一个字符，那么右端点j的位置如何变化？显然j必然是右移才行。由此发现，i和j都只需要单调右移，就可以找遍所有符合条件的子区间。故快慢指针即可解此题。

我们需要一个辅助函数，判断一个区间内的字符是否符合条件。因为本题只有小写因为字母，所以只需要开一个长度为26的计数器，存储滑窗里各个字符的频次，与word2的频次逐一比对即可。

这样的做法时间复杂度是o(26n).

解法2

辅助函数可以进一步优化。事实上，我们不需要将26个字符的频次逐一比对。我们只需要再加一个计数器t，持续更新迄今为止有多少字符的频次已经满足要求。更新的规则是：

1. 当word[j]加入区间时，如果count[word[j]]==target[word[j]]，那么t可以增一。
2. 当word[i]移出区间时，如果count[word[i]]==target[word[i]]-1，那么t可以增一。 其他情况下t都不需要变化。当任何时候，如果t等于word2的字符种类数T时，就一定意味着区间内的所有字符频次都符合要求。

这样的做法时间复杂度是o(n).