刷题笔记合集🔗

冗余覆盖

问题描述

给定两个字符串 和 和正整数 ，其中 长度为 ， 长度为 ，在 中选一个子串，满足:

• 该子串长度为
• 该子串中包含 中全部字母
• 该子串每个字母出现次数不小于 中对应的字母

我们称 以长度 冗余覆盖 ，给定 ，，，求最左侧的 以长度 冗余覆盖 的子串的首个元素的下标，如果没有返回**-1**。

输入格式

输入三行，第一行为 ，第二行为 ，第三行为 ， 和 只包含小写字母。

输出格式

最左侧的 以长度 冗余覆盖 的子串首个元素下标，如果没有返回**-1**。

样例输入

ab
aabcd
1

样例输出

0

数据范围

• 和 只包含小写字母

题解

这道题是一个典型的滑动窗口问题，需要在 中找到一个满足特定条件的子串。

关键思路如下：

1. 首先统计 中每个字符的出现次数。
2. 使用滑动窗口在 中寻找长度为 的子串，检查这个子串是否满足覆盖条件。
3. 覆盖条件是：子串中包含 中的所有字符，且每个字符出现的次数不少于 中的对应字符。

具体实现上，可以用一个计数器来跟踪还需要匹配的字符数量。当窗口内某个字符的出现次数达到 中该字符的出现次数时，计数器减少。当计数器变为0时，表示找到了满足条件的子串。

在滑动窗口的过程中，我们需要用差异更新的思想来高效处理窗口的移动：

• 当窗口右移时，右边界新加入一个字符，左边界移出一个字符
• 我们只需要处理这两个字符对计数器的影响，而不需要重新统计整个窗口内的所有字符

算法的时间复杂度是 ，其中 是 的长度。因为我们最多需要滑动窗口 次，且每次处理的操作是常数级别的。

空间复杂度是 ，其中 是字符集的大小（本题中是小写字母，所以 ）。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入处理
s1 = input()
s2 = input()
k = int(input())

def find_substring(s1, s2, k):
    # 获取字符串长度
    n1 = len(s1)
    n2 = len(s2)
    
    # 判断是否可能存在符合条件的子串
    if n2 < n1 + k:
        return -1
    
    # 统计s1中字符出现次数
    char_count = {}
    for c in s1:
        if c in char_count:
            char_count[c] += 1
        else:
            char_count[c] = 1
    
    # 需要匹配的字符总数
    remain = n1
    
    # 目标子串长度
    target_len = n1 + k
    
    # 检查从索引0开始的子串
    for j in range(target_len):
        c = s2[j]
        if c in char_count:
            # 字符c在s1中存在
            char_count[c] -= 1
            # 如果减1后count还>=0，说明这个字符是需要匹配的字符
            if char_count[c] >= 0:
                remain -= 1
    
    # 如果remain=0，说明所有s1中的字符都已被匹配
    if remain == 0:
        return 0
    
    # 滑动窗口，检查其他位置
    for i in range(1, n2 - target_len + 1):
        # 移出窗口左侧字符
        left_char = s2[i - 1]
        if left_char in char_count:
            if char_count[left_char] >= 0:
                remain += 1
            char_count[left_char] += 1
        
        # 移入窗口右侧字符
        right_char = s2[i + target_len - 1]
        if right_char in char_count:
            char_count[right_char] -= 1
            if char_count[right_char] >= 0:
                remain -= 1
        
        # 如果remain=0，说明找到满足条件的子串
        if remain == 0:
            return i
    
    return -1

# 输出结果
print(find_substring(s1, s2, k))

• Cpp

#include <bits