3297. 统计重新排列后包含另一个字符串的子字符串数目 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^5
• 1 <= word2.length <= 10^4
• word1 和 word2 都只包含小写英文字母。

Reference

题解

word1上的一个区间划定了一个子字符串，如果这个子字符串是合法的，那么称这个区间是合法的。要判断子字符串合法，只需word1在该区间内出现的各个字符数量多于word2中的各个字符数量，即：

def check(self, word1: Dict[str, int], word2: Dict[str, int]):
    for k, v in word2.items():
        if word1.get(k, 0) < v:
            return False
    return True

使用双指针法：

• 如果一个区间[l:r]范围是合法的，那么，后续的所有区间[l: r + 1]直到[l:]都是合法的。
• 如果一个区间[l:r]范围不是合法的，那么，将l向前移动的所有区间[l + 1: r]直到[r: r]都不是合法的。

因此，可以从区间[0:0]出发，先向右移动右端点，找到一个合法区间，之后后续的区间则全都是合法的。下一步移动左端点，每一次移动检查一下当前区间是否合法，如果合法则记录当前区间和后续的所有区间，不断移动直到当前区间不再合法，此后重新开始移动右端点。

class Solution:
    def check(self, word1: Dict[str, int], word2: Dict[str, int]):
        for k, v in word2.items():
            if word1.get(k, 0) < v:
                return False
        return True

    def validSubstringCount(self, word1: str, word2: str) -> int:
        l, r, current = 0, 0, {}
        length, word2_counter = len(word1), {}
        for char in word2:
            word2_counter[char] = word2_counter.get(char, 0) + 1

        result = 0
        while r < length:
            while r < length and not self.check(current, word2_counter):
                current[word1[r]] = current.get(word1[r], 0) + 1
                r += 1

            while self.check(current, word2_counter):
                result += length - r + 1
                current[word1[l]] -= 1
                l += 1

        return result

以上的代码在每次判断合法时都需要遍历一遍所有出现的字符，开销较大。实际上我们只需要根据用一个变量non_zero记录word2里出现次数多于word1中的字符数量。每次移动区间的时候仅仅更新non_zero即可。

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        l, r = 0, 0
        length, word2_counter = len(word1), {}
        for char in word2:
            word2_counter[char] = word2_counter.get(char, 0) + 1
        non_zeros = len(word2_counter)

        result = 0
        while r < length:
            while r < length and non_zeros:
                if word1[r] in word2_counter:
                    word2_counter[word1[r]] -= 1
                    if word2_counter[word1[r]] == 0:
                        non_zeros -= 1
                r += 1

            while not non_zeros:
                result += length - r + 1
                if word1[l] in word2_counter:
                    word2_counter[word1[l]] += 1
                    if word2_counter[word1[l]] == 1:
                        non_zeros += 1
                l += 1

        return result

评论