【华为OD-E卷-最左侧冗余覆盖子串 100分（python、java、c++、js、c）】

题目

给定两个字符串 s1 和 s2 和正整数 k，其中 s1 长度为 n1，s2 长度为 n2。
在 s2 中选一个子串，若满足下面条件，则称 s2 以长度 k 冗余覆盖 s1
该子串长度为 n1 + k
该子串中包含 s1 中全部字母
该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1，s2，k，求最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素的下标，如果没有返回-1。
举例：
s1 = “ab”
s2 = “aabcd”
k = 1
则子串 “aab” 和 “abc” 均满足此条件，由于 “aab” 在 “abc” 的左侧，“aab” 的第一个元素下部为 0，因此输出 0

输入描述

• 输入三行，第一行为 s1，第二行为 s2，第三行为 k

s1 和 s2 只包含小写字母

输出描述

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

备注

• 0 ≤ len(s1) ≤ 1000000 0 ≤ len(s2) ≤ 20000000 0 ≤ k ≤ 1000

用例

用例一：

输入：

ab
aabcd
1

• 1
• 2
• 3

输出：

0

• 1

用例二：

输入：

abc
dfs
10

• 1
• 2
• 3

输出：

-1

• 1

python解法

• 解题思路：
• 该问题要求判断字符串 s1 是否可以通过在字符串 s2 的子串中找到一种排列，并允许在 s1 的排列前后插入至多 k 个字符。问题的核心是滑动窗口算法，以下是具体的思路：

窗口的定义：窗口长度为 len(s1) + k，因为允许在 s1 的排列前后插入至多 k 个字符。
字符计数：使用哈希表 need 来记录 s1 中每个字符的需求量，同时维护一个变量 total，表示 s1 中剩余未匹配的字符总数。
滑动窗口匹配：初始时，滑动窗口覆盖 s2 的前 len(s1) + k 个字符，判断是否满足条件。
动态调整窗口：通过移出窗口的第一个字符（out_char）和加入窗口的最后一个字符（in_char），动态更新 need 和 total，同时检查是否匹配。
结果返回：如果在任意位置找到满足条件的子串，返回其起始索引；否则返回 -1。

def find_substring(s1, s2, k):
    # 获取 s1 和 s2 的长度
    n1, n2 = len(s1), len(s2)
    
    # 如果 s2 长度不足以容纳 s1 和 k 个额外字符，直接返回 -1
    if n2 < n1 + k:
        return -1
    
    # 初始化 need 字典，记录 s1 中每个字符的需求量
    need = {char: s1.count(char) for char in set(s1)}
    # 记录 s1 中未匹配的字符总数
    total = len(s1)
    
    # 初始化窗口，检查前 n1 + k 个字符
    for i in range(n1 + k):
        if s2[i] in need:  # 如果字符在需要的列表中
            if need[s2[i]] > 0:  # 若还需要该字符，减少总需求量
                total -= 1
            need[s2[i]] -= 1  # 减少该字符的需求量
        if total == 0:  # 若匹配成功，直接返回起始索引
            return 0
    
    # 滑动窗口从索引 1 开始
    for i in range(1, n2 - n1 - k + 1):
        # 移出窗口的字符
        out_char = s2[i - 1]
        # 加入窗口的字符
        in_char = s2[i + n1 + k - 1]
        
        # 处理移出的字符
        if out_char in need:
            if need[out_char] >= 0:  # 如果原本在匹配中，增加总需求量
                total += 1
            need[out_char] += 1  # 恢复该字符的需求量
        
        # 处理加入的字符
        if in_char in need:
            if need[in_char] > 0:  # 若该字符还需要，减少总需求量
                total -= 1
            need[in_char] -= 1  # 减少该字符的需求量
        
        # 如果匹配成功，返回起始索引
        if total == 0:
            return i
    
    # 若未找到匹配的子串，返回 -1
    return -1

# 输入 s1, s2 和 k
s1 = input()
s2 = input()
k = int(input())
# 输出结果
print(find_substring(s1, s2, k))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55

java解法

• 解题思路
• 该问题与之前的解法类似，需要在字符串 mainStr 中找到一个子串，该子串可以通过调整为字符串 subStr 的排列，且允许在子串前后插入至多 extraLen 个额外字符。为此，问题可以通过滑动窗口和字符频率计数器来解决。

具体思路：

初始化字符频率表： 使用一个大小为 128 的数组 freqMap 来记录 subStr 中各字符的需求量。
初始化窗口： 首先处理 mainStr 的前 subLen + extraLen 个字符（初始窗口），检查是否已经满足条件。
动态调整窗口：
滑动窗口时，每次移除窗口起点字符，加入窗口终点字符，动态调整 freqMap 和未匹配字符的计数 missingCount。
检查匹配条件： 当 missingCount == 0 时，表示窗口内的字符可以通过排列形成 subStr，返回当前窗口起始索引。
无匹配返回 -1： 如果所有窗口均不满足条件，则返回 -1。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入：子串、主串以及允许的额外字符长度
        String subStr = sc.next();
        String mainStr = sc.next();
        int extraLen = sc.nextInt();

        // 输出结果
        System.out.println(findMinIndex(subStr, mainStr, extraLen));
    }

    public static int findMinIndex(String subStr, String mainStr, int extraLen) {
        // 获取子串和主串的长度
        int subLen = subStr.length();
        int mainLen = mainStr.length();
        
        // 如果主串长度不足以容纳子串和额外字符，直接返回 -1
        if (mainLen < subLen + extraLen) return -1;

        // 初始化字符频率表，记录子串中每个字符的需求量
        int[] freqMap = new int[128];
        for (int i = 0; i < subLen; i++) {
            freqMap[subStr.charAt(i)]++;
        }

        // 记录未匹配的字符总数
        int missingCount = subLen;
        // 定义滑动窗口的最大起始索引
        int maxIndex = mainLen - subLen - extraLen;
        // 定义窗口长度
        int targetLen = subLen + extraLen;

        // 初始化窗口，检查前 targetLen 个字符
        for (int j = 0; j < targetLen; j++) {
            if (--freqMap[mainStr.charAt(j)] >= 0) { // 如果字符需求量未负，减少未匹配数量
                missingCount--;
            }

            // 如果未匹配数量为 0，表示找到匹配的窗口
            if (missingCount == 0) {
                return 0;
            }
        }

        // 滑动窗口，动态调整
        for (int i = 1; i <= maxIndex; i++) {
            // 移出窗口的字符，恢复其需求量
            if (++freqMap[mainStr.charAt(i - 1)] > 0) { 
                missingCount++;
            }
            // 加入窗口的字符，减少其需求量
            if (--freqMap[mainStr.charAt(i + targetLen - 1)] >= 0) {
                missingCount--;
            }

            // 如果未匹配数量为 0，返回当前窗口起始索引
            if (missingCount == 0) {
                return i;
            }
        }

        // 如果没有找到匹配，返回 -1
        return -1;
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70

C++解法

• 解题思路
• 该问题要求在字符串 s2 中找到一个子串，使其包含字符串 s1 的所有字符，且允许在前后插入最多 k 个额外字符。为此，可以通过滑动窗口和字符频率计数的方式解决。

具体思路：

初始化字符频率表： 使用两个数组 cnt1 和 win 分别记录 s1 的字符频率和当前窗口的字符频率。
匹配计数器： 使用变量 match 记录窗口中与 s1 对应字符频率匹配的字符数量。
窗口初始化： 窗口长度为 len1 + k，初始时将 s2 的前 len1 + k 个字符加入窗口。
滑动窗口： 每次移动窗口：
加入新的字符，更新窗口频率，并检查是否增加匹配字符数量。
移除旧字符，更新窗口频率，并检查是否减少匹配字符数量。
匹配判断： 当 match == len1 时，表示窗口中字符完全覆盖了 s1 的所有字符，返回当前窗口的起始索引。
无匹配返回： 若遍历所有窗口后仍未找到匹配，返回 -1。

#include 
#include 
#include 

using namespace std;

// 在字符串 s2 中寻找满足条件的子串起始索引
int findSubstr(string s1, string s2, int k) {
    int len1 = s1.size(); // s1 的长度
    int len2 = s2.size(); // s2 的长度

    // 如果 s2 的长度不足以容纳 s1 和额外的 k 个字符，直接返回 -1
    if (len2 < len1 + k) return -1;

    // 初始化字符频率表：cnt1 记录 s1 中字符的需求量，win 记录窗口中字符的频率
    vector<int> cnt1(128, 0), win(128, 0);
    for (char c : s1) {
        cnt1[c]++;
    }

    // 记录匹配字符的数量
    int match = 0;
    // 窗口长度为 len1 + k
    int winLen = len1 + k;

    // 遍历字符串 s2
    for (int i = 0; i < len2; i++) {
        // 添加当前字符到窗口中
        if (win[s2[i]]++ < cnt1[s2[i]]) match++;

        // 当窗口长度超过 winLen 时，移除最左边的字符
        if (i >= winLen) {
            if (--win[s2[i - winLen]] < cnt1[s2[i - winLen]]) match--;
        }

        // 如果匹配字符数量等于 s1 的长度，返回当前窗口的起始索引
        if (match == len1) return i - winLen + 1;
    }

    // 如果未找到匹配的子串，返回 -1
    return -1;
}

int main() {
    string s1, s2;
    int k;

    // 输入子串 s1、主串 s2 和允许的额外字符长度 k
    cin >> s1 >> s2 >> k;

    // 输出结果
    cout << findSubstr(s1, s2, k) << endl;

    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56

C解法

• 解题思路

更新中

• 1

JS解法

• 解题思路

• 本问题的目标是在字符串 s2 中找到一个子串，使其包含字符串 s1 的所有字符，并允许在前后插入最多 k 个额外字符。使用滑动窗口和字符计数的方法来实现。以下是具体思路：

初始化字符计数器：
使用哈希表 count 记录字符串 s1 中每个字符的需求频率。
窗口匹配计数器：
使用变量 missing 表示当前窗口中未匹配的 s1 中的字符数量。
初始化窗口：
窗口长度为 len1 + k，初始时将 s2 的前 len1 + k 个字符加入窗口，并动态更新 missing。
滑动窗口：
每次滑动窗口时，移出窗口的第一个字符，加入窗口的最后一个字符，同时更新 count 和 missing。
检查匹配条件：
当 missing == 0 时，表示窗口内字符完全覆盖了 s1 的所有字符，返回当前窗口的起始索引。
无匹配返回：
若遍历所有窗口后未找到匹配，返回 -1。

const readline = require("readline");

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

const input = [];

rl.on("line", (line) => {
    input.push(line);
    if (input.length === 3) {
        const [s1, s2, k] = input;
        console.log(findMinIndex(s1, s2, parseInt(k)));
        input.length = 0;
    }
});

// 查找满足条件的子串的起始索引
function findMinIndex(s1, s2, k) {
    const len1 = s1.length; // s1 的长度
    const len2 = s2.length; // s2 的长度

    // 如果 s2 的长度不足以容纳 s1 和额外的 k 个字符，直接返回 -1
    if (len2 < len1 + k) return -1;

    // 初始化字符需求计数器
    const count = {};
    for (let ch of s1) {
        count[ch] = (count[ch] || 0) + 1;
    }

    // 初始化未匹配字符计数
    let missing = len1;
    // 窗口大小为 len1 + k
    const windowSize = len1 + k;

    // 初始化窗口，检查前 windowSize 个字符
    for (let i = 0; i < windowSize; i++) {
        const ch = s2[i];
        if (count[ch] !== undefined) { // 如果字符在需求表中
            if (count[ch] > 0) missing--; // 若字符仍被需求，减少未匹配计数
            count[ch]--; // 减少字符需求量
        }
        if (missing === 0) return 0; // 如果匹配成功，返回起始索引
    }

    // 滑动窗口，动态调整
    for (let i = 1; i <= len2 - windowSize; i++) {
        // 移出窗口的字符
        const toRemove = s2[i - 1];
        if (count[toRemove] !== undefined) { // 如果移出字符在需求表中
            if (count[toRemove] >= 0) missing++; // 若字符原本满足需求，增加未匹配计数
            count[toRemove]++; // 恢复字符需求量
        }

        // 加入窗口的字符
        const toAdd = s2[i - 1 + windowSize];
        if (count[toAdd] !== undefined) { // 如果加入字符在需求表中
            if (count[toAdd] > 0) missing--; // 若字符仍被需求，减少未匹配计数
            count[toAdd]--; // 减少字符需求量
        }

        // 如果匹配成功，返回当前窗口起始索引
        if (missing === 0) return i;
    }

    // 如果未找到匹配的子串，返回 -1
    return -1;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏