刷题笔记合集🔗

最左侧冗余覆盖子串

问题描述

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

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

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

输入格式

输入三行：

• 第一行为字符串
• 第二行为字符串
• 第三行为整数

和 只包含小写字母。

输出格式

输出一个整数，表示最左侧的 以长度 冗余覆盖 的子串首个元素下标，如果没有返回 -1。

样例输入

ab
aabcd
1

样例输出

0

样例解释

无

数据范围

题解

这道题目本质上是一个滑动窗口问题，。解题思路如下：

1. 首先，统计 中每个字符的出现次数。
2. 使用滑动窗口在 上移动，窗口大小为 。
3. 对于每个窗口，统计窗口内字符的出现次数。
4. 比较窗口内的字符统计与 的字符统计，检查是否满足冗余覆盖的条件。
5. 如果满足条件，返回窗口的起始索引；如果遍历完所有窗口都不满足，返回 -1。

关键点解释：

• 使用数组或哈希表来存储字符计数，可以快速进行比较。
• 滑动窗口技巧可以避免重复计算，提高效率。

时间复杂度分析：

• 统计 的字符次数：
• 滑动窗口遍历 ：
• 每次窗口移动时的字符计数比较：（因为只有小写字母）

总体时间复杂度：

参考代码

• Python

def check_redundancy(s1_count, window_count):
    """
    检查窗口是否冗余覆盖s1
    """
    return all(window_count.get(c, 0) >= s1_count[c] for c in s1_count)

def find_redundant_substring(s1, s2, k):
    """
    寻找s2中冗余覆盖s1的子串
    """
    n1, n2 = len(s1), len(s2)
    window_size = n1 + k
    
    if window_size > n2:
        return -1
    
    # 统计s1中字符出现次数
    s1_count = {}
    for c in s1:
        s1_count[c] = s1_count.get(c, 0) + 1
    
    # 初始化窗口
    window_count = {}
    for c in s2[:window_size]:
        window_count[c] = window_count.get(c, 0) + 1
    
    # 检查第一个窗口
    if check_redundancy(s1_count, window_count):
        return 0
    
    # 滑动窗口
    for i in range(1, n2 - window_size + 1):
        # 移除窗口左边的字符
        window_count[s2[i-1]] -= 1
        if window_count[s2[i-1]] == 0:
            del window_count[s2[i-1]]
        
        # 添加窗口右边的新字符
        window_count[s2[i+window_size-1]] = window_count.get(s2[i+window_size-1], 0) + 1
        
        # 检查当前窗口
        if check_redundancy(s1_count, window_count):
            return i
    
    return -1

# 读取输入
s1 = input().strip()
s2 = input().strip()
k = int(input())

# 计算并输出结果
result = find_redundant_substring(s1, s2, k)
print(result)

• C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_LEN 100001

bool check_redundancy(int s1_count[], int window_count[]) {
    for (int i = 0; i < 26; i++) {
        if (window_count[i] < s1_count[i]) {
            return false;
        }
    }
    return true;
}

int find_redundant_substring(char s1[], char s2[], int k) {
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    int window_size = n1 + k;
    
    if (window_size > n2) {
        return -1;
    }
    
    int s1_count[26] = {0};
    int window_count[26] = {0};
    
    // 统计s1中字符出现次数
    for (int i = 0; i < n1; i++) {
        s1_count[s1[i] - 'a']++;
    }
    
    // 初始化窗口
    for (int i = 0; i < window_size; i++) {
        window_count[s2[i] - 'a']++;
    }
    
    // 检查第一个窗口
    if (check_redundancy(s1_count, window_count)) {
        return 0;
    }
    
    // 滑动窗口
    for (int i = 1; i <= n2 - window_size; i++) {
        window_count[s2[i-1] - 'a']--;
        window_count[s2[i+window_size-1] - 'a']++;
        
        if (check_redundancy(s1_count, window_count)) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char s1[MAX_LEN], s2[MAX_LEN];
    int k;
    
    scanf("%s", s1);
    scanf("%s", s2);
    scanf("%d", &k);
    
    int result = find_redundant_substring(s1, s2, k);
    printf("%d\n", result);
    
    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];

rl.on('line', (line) => {
    lines.push(line);
    if (l