E卷-最左侧冗余覆盖子串(100分)

最左侧冗余覆盖子串

问题描述

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

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

我们称 以长度 冗余覆盖 ，给定 ，，，求最左侧的 以长度 冗余覆盖 的子串的首个元素的下标，如果没有返回 -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 (lines.length === 3) {
        const [s1, s2, k] = lines;
        console.log(findRedundantSubstring(s1, s2, parseInt(k)));
        rl.close();
    }
});

function checkRedundancy(s1Count, windowCount) {
    for (let c in s1Count) {
        if ((windowCount[c] || 0) < s1Count[c]) {
            return false;
        }
    }
    return true;
}

function findRedundantSubstring(s1, s2, k) {
    const n1 = s1.length;
    const n2 = s2.length;
    const windowSize = n1 + k;
    
    if (windowSize > n2) {
        return -1;
    }
    
    const s1Count = {};
    const windowCount = {};
    
    // 统计s1中字符出现次数
    for (let c of s1) {
        s1Count[c] = (s1Count[c] || 0) + 1;
    }
    
    // 初始化窗口
    for (let i = 0; i < windowSize; i++) {
        windowCount[s2[i]] = (windowCount[s2[i]] || 0) + 1;
    }
    
    // 检查第一个窗口
    if (checkRedundancy(s1Count, windowCount)) {
        return 0;
    }
    
    // 滑动窗口
    for (let i = 1; i <= n2 - windowSize; i++) {
        windowCount[s2[i-1]]--;
        if (windowCount[s2[i-1]] === 0) {
            delete windowCount[s2[i-1]];
        }
        windowCount[s2[i+windowSize-1]] = (windowCount[s2[i+windowSize-1]] || 0) + 1;
        
        if (checkRedundancy(s1Count, windowCount)) {
            return i;
        }
    }
    
    return -1;
}

• Java

import java.util.*;

public class Main {
    public static boolean checkRedundancy(Map<Character, Integer> s1Count, Map<Character, Integer> windowCount) {
        for (char c : s1Count.keySet()) {
            if (windowCount.getOrDefault(c, 0) < s1Count.get(c)) {
                return false;
            }
        }
        return true;
    }
    
    public static int findRedundantSubstring(String s1, String s2, int k) {
        int n1 = s1.length();
        int n2 = s2.length();
        int windowSize = n1 + k;
        
        if (windowSize > n2) {
            return -1;
        }
        
        Map<Character, Integer> s1Count = new HashMap<>();
        Map<Character, Integer> windowCount = new HashMap<>();
        
        // 统计s1中字符出现次数
        for (char c : s1.toCharArray()) {
            s1Count.put(c, s1Count.getOrDefault(c, 0) + 1);
        }
        
        // 初始化窗口
        for (int i = 0; i < windowSize; i++) {
            char c = s2.charAt(i);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
        }
        
        // 检查第一个窗口
        if (checkRedundancy(s1Count, windowCount)) {
            return 0;
        }
        
        // 滑动窗口
        for (int i = 1; i <= n2 - windowSize; i++) {
            char removeChar = s2.charAt(i - 1);
            char addChar = s2.charAt(i + windowSize - 1);
            
            windowCount.put(removeChar, windowCount.get(removeChar) - 1);
            if (windowCount.get(removeChar) == 0) {
                windowCount.remove(removeChar);
            }
            windowCount.put(addChar, windowCount.getOrDefault(addChar, 0) + 1);
            
            if (checkRedundancy(s1Count, windowCount)) {
                return i;
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        int k = scanner.nextInt();
        
        int result = findRedundantSubstring(s1, s2, k);
        System.out.println(result);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

bool checkRedundancy(const unordered_map<char, int>& s1Count, const unordered_map<char, int>& windowCount) {
    for (const auto& pair : s1Count) {
        if (windowCount.find(pair.first) == windowCount.end() || windowCount.at(pair.first) < pair.second) {
            return false;
        }
    }
    return true;
}

int findRedundantSubstring(const string& s1, const string& s2, int k) {
    int n1 = s1.length();
    int n2 = s2.length();
    int windowSize = n1 + k;
    
    if (windowSize > n2) {
        return -1;
    }
    
    unordered_map<char, int> s1Count, windowCount;
    
    // 统计s1中字符出现次数
    for (char c : s1) {
        s1Count[c]++;
    }
    
    // 初始化窗口
    for (int i = 0; i < windowSize; i++) {
        windowCount[s2[i]]++;
    }
    
    // 检查第一个窗口
    if (checkRedundancy(s1Count, windowCount)) {
        return 0;
    }
    
    // 滑动窗口
    for (int i = 1; i <= n2 - windowSize; i++) {
        windowCount[s2[i-1]]--;
        if (windowCount[s2[i-1]] == 0) {
            windowCount.erase(s2[i-1]);
        }
        windowCount[s2[i+windowSize-1]]++;
        
        if (checkRedundancy(s1Count, windowCount)) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    string s1, s2;
    int k;
    
    // 读取输入
    cin >> s1 >> s2 >> k;
    
    // 计算并输出结果
    int result = findRedundantSubstring(s1, s2, k);
    cout << result << endl;
    
    return 0;
}