可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

相关推荐阅读

题目练习网址：【固定滑窗】2025C-最左侧冗余覆盖子串

题目描述与示例

题目描述

给定两个字符串 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) ≤ 100000
  • 0 ≤ len(s2) ≤ 200000
  • 0 ≤ k ≤ 1000

示例一

输入

ab
aabcd
1

输出

0

说明

子串aab和abc符合要求，由于aab在abc的左侧，因此输出aab的下标：0

示例二

输入

abc
dfs
10

输出

-1

说明

s2`无法覆盖`s1`，输出 `-1

解题思路

本题是LeetCode 76、最小覆盖子串 的固定滑窗版本，直接使用三问三答即可直接解决。

在代码层面，本题和【固定滑窗】2024E-关联字串也非常相似，可以在一起进行比较。

区别在于

  • 固定滑窗的的长度win_len从n1修改为了n1+k，表示窗口长度包含长度k的冗余
  • check()函数的==修改为了<=，表示s2的子串需要覆盖s1而非和s1的排列全等

剩下的内容几乎和【固定滑窗】2025B-关联字串完全相同。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：【固定滑窗】2024E/2025B/2025C-最左侧冗余覆盖子串
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：固定滑窗
# 代码看不懂的地方，请直接在群上提问


# 检查ans_cnt中出现的元素频率是否均小于等于win_cnt中的函数
def check(win_cnt, ans_cnt):
    return all(v <= win_cnt[k] for k, v in ans_cnt.items())

from collections import Counter

# 输入s1, s2, k
s1 = input()
s2 = input()
k = int(input())
# 初始化答案为-1
ans = -1
# 获得两个字符串的长度n1和n2
n1, n2 = len(s1), len(s2)
# 固定滑窗的长度win_len = k + n1
win_len = k + n1
# 初始化s2中第一个窗口的元素频率
win_cnt = Counter(s2[:win_len])
# 初始化s1的元素频率，是需要被覆盖的元素频率
ans_cnt = Counter(s1)
# 如果第一个窗口就覆盖，直接得到结果
if check(win_cnt, ans_cnt):
    ans = 0
# 否则进行固定滑窗过程
else:
    for right, ch in enumerate(s2[win_len:], win_len):
        # A1
        win_cnt[ch] += 1
        # A2
        win_cnt[s2[right - win_len]] -= 1
        # A3
        # 找到答案可以直接退出
        if check(win_cnt, ans_cnt):
            ans = right - win_len + 1
            break

print(ans)

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    // 检查 ansCnt 中出现的元素频率是否均小于等于 winCnt 中的函数
    public static boolean check(Map<Character, Integer> winCnt, Map<Character, Integer> ansCnt) {
        for (Map.Entry<Character, Integer> entry : ansCnt.entrySet()) {
            if (entry.getValue() > winCnt.getOrDefault(entry.getKey(), 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入 s1, s2, k
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        int k = scanner.nextInt();
        scanner.close();

        // 初始化答案为 -1
        int ans = -1;
        int n1 = s1.length();
        int n2 = s2.length();
        int winLen = k + n1; // 固定滑窗的长度 winLen = k + n1

        // 初始化 s2 中第一个窗口的元素频率
        Map<Character, Integer> winCnt = new HashMap<>();
        for (int i = 0; i < winLen && i < n2; i++) {
            winCnt.put(s2.charAt(i), winCnt.getOrDefault(s2.charAt(i), 0) + 1);
        }

        // 初始化 s1 的元素频率，是需要被覆盖的元素频率
        Map<Character, Integer> ansCnt = new HashMap<>();
        for (char ch : s1.toCharArray()) {
            ansCnt.put(ch, ansCnt.getOrDefault(ch, 0) + 1);
        }

        // 如果第一个窗口就覆盖，直接得到结果
        if (check(winCnt, ansCnt)) {
            ans = 0;
        } else {
            // 否则进行固定滑窗过程
            for (int right = winLen; right < n2; right++) {
                char addChar = s2.charAt(right); // A1
                winCnt.put(addChar, winCnt.getOrDefault(addChar, 0) + 1);

                char removeChar = s2.charAt(right - winLen); // A2
                winCnt.put(removeChar, winCnt.get(removeChar) - 1);
                if (winCnt.get(removeChar) == 0) {
                    winCnt.remove(removeChar);
                }

                // 找到答案可以直接退出
                if (check(winCnt, ansCnt)) { // A3
                    ans = right - winLen + 1;
                    break;
                }
            }
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

// 检查 ansCnt 中出现的元素频率是否均小于等于 winCnt 中的函数
bool check(const unordered_map<char, int>& winCnt, const unordered_map<char, int>& ansCnt) {
    for (const auto& [key, value] : ansCnt) {
        if (winCnt.find(key) == winCnt.end() || winCnt.at(key) < value) {
            return false;
        }
    }
    return true;
}

int main() {
    string s1, s2;
    int k;
    // 输入 s1, s2, k
    cin >> s1 >> s2 >> k;

    // 初始化答案为 -1
    int ans = -1;
    int n1 = s1.size();
    int n2 = s2.size();
    int winLen = k + n1; // 固定滑窗的长度 winLen = k + n1

    // 初始化 s2 中第一个窗口的元素频率
    unordered_map<char, int> winCnt;
    for (int i = 0; i < winLen && i < n2; i++) {
        winCnt[s2[i]]++;
    }

    // 初始化 s1 的元素频率，是需要被覆盖的元素频率
    unordered_map<char, int> ansCnt;
    for (char ch : s1) {
        ansCnt[ch]++;
    }

    // 如果第一个窗口就覆盖，直接得到结果
    if (check(winCnt, ansCnt)) {
        ans = 0;
    } else {
        // 否则进行固定滑窗过程
        for (int right = winLen; right < n2; right++) {
            char addChar = s2[right]; // A1
            winCnt[addChar]++;

            char removeChar = s2[right - winLen]; // A2
            if (--winCnt[removeChar] == 0) {
                winCnt.erase(removeChar);
            }

            // 找到答案可以直接退出
            if (check(winCnt, ansCnt)) { // A3
                ans = right - winLen + 1;
                break;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

C

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

#define MAX_CHAR 26

// 检查 ans_cnt 中出现的元素频率是否均小于等于 win_cnt 中的函数
bool check(int win_cnt[], int ans_cnt[]) {
    for (int i = 0; i < MAX_CHAR; i++) {
        if (ans_cnt[i] > win_cnt[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    char s1[100001], s2[200001];
    int k;
    // 输入 s1, s2, k
    scanf("%s", s1);
    scanf("%s", s2);
    scanf("%d", &k);

    int n1 = strlen(s1);
    int n2 = strlen(s2);
    int win_len = k + n1; // 固定滑窗的长度 win_len = k + n1
    int ans = -1;

    // 初始化 s2 中第一个窗口的元素频率
    int win_cnt[MAX_CHAR] = {0};
    for (int i = 0; i < win_len && i < n2; i++) {
        win_cnt[s2[i] - 'a']++;
    }

    // 初始化 s1 的元素频率，是需要被覆盖的元素频率
    int ans_cnt[MAX_CHAR] = {0};
    for (int i = 0; i < n1; i++) {
        ans_cnt[s1[i] - 'a']++;
    }

    // 如果第一个窗口就覆盖，直接得到结果
    if (check(win_cnt, ans_cnt)) {
        ans = 0;
    } else {
        // 否则进行固定滑窗过程
        for (int right = win_len; right < n2; right++) {
            // A1：将 s2[right] 加入窗口
            win_cnt[s2[right] - 'a']++;

            // A2：移出窗口左侧字符
            win_cnt[s2[right - win_len] - 'a']--;

            // A3：检查是否满足条件，找到答案则退出
            if (check(win_cnt, ans_cnt)) {
                ans = right - win_len + 1;
                break;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

Node JavaScript

const readline = require("readline");

// 检查 ans_cnt 中出现的元素频率是否均小于等于 win_cnt 中的函数
function check(winCnt, ansCnt) {
    for (let i = 0; i < 26; i++) {
        if (ansCnt[i] > winCnt[i]) {
            return false;
        }
    }
    return true;
}

// 读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on("line", line => {
    lines.push(line);
    if (lines.length === 3) {
        rl.close();
    }
});

rl.on("close", () => {
    const s1 = lines[0];
    const s2 = lines[1];
    const k = parseInt(lines[2], 10);

    const n1 = s1.length;
    const n2 = s2.length;
    const winLen = k + n1; // 固定滑窗的长度 winLen = k + n1
    let ans = -1;

    // 初始化 s2 中第一个窗口的元素频率
    const winCnt = Array(26).fill(0);
    for (let i = 0; i < winLen && i < n2; i++) {
        winCnt[s2.charCodeAt(i) - 97]++;
    }

    // 初始化 s1 的元素频率，是需要被覆盖的元素频率
    const ansCnt = Array(26).fill(0);
    for (let ch of s1) {
        ansCnt[ch.charCodeAt(0) - 97]++;
    }

    // 如果第一个窗口就覆盖，直接得到结果
    if (check(winCnt, ansCnt)) {
        ans = 0;
    } else {
        // 否则进行固定滑窗过程
        for (let right = winLen; right < n2; right++) {
            // A1：将 s2[right] 加入窗口
            winCnt[s2.charCodeAt(right) - 97]++;

            // A2：移出窗口左侧字符
            winCnt[s2.charCodeAt(right - winLen) - 97]--;

            // A3：检查是否满足条件，找到答案则退出
            if (check(winCnt, ansCnt)) {
                ans = right - winLen + 1;
                break;
            }
        }
    }

    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

const maxChar = 26

// 检查 ansCnt 中出现的元素频率是否均小于等于 winCnt 中的函数
func check(winCnt, ansCnt [maxChar]int) bool {
    for i := 0; i < maxChar; i++ {
        if ansCnt[i] > winCnt[i] {
            return false
        }
    }
    return true
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    s1, _ := reader.ReadString('\n')
    s2, _ := reader.ReadString('\n')
    kStr, _ := reader.ReadString('\n')

    s1 = strings.TrimSpace(s1)
    s2 = strings.TrimSpace(s2)
    k, _ := strconv.Atoi(strings.TrimSpace(kStr))

    n1 := len(s1)
    n2 := len(s2)
    winLen := k + n1 // 固定滑窗的长度 winLen = k + n1
    ans := -1

    // 初始化 s2 中第一个窗口的元素频率
    var winCnt [maxChar]int
    for i := 0; i < winLen && i < n2; i++ {
        winCnt[s2[i]-'a']++
    }

    // 初始化 s1 的元素频率，是需要被覆盖的元素频率
    var ansCnt [maxChar]int
    for _, ch := range s1 {
        ansCnt[ch-'a']++
    }

    // 如果第一个窗口就覆盖，直接得到结果
    if check(winCnt, ansCnt) {
        ans = 0
    } else {
        // 否则进行固定滑窗过程
        for right := winLen; right < n2; right++ {
            // A1：将 s2[right] 加入窗口
            winCnt[s2[right]-'a']++

            // A2：移出窗口左侧字符
            winCnt[s2[right-winLen]-'a']--

            // A3：检查是否满足条件，找到答案则退出
            if check(winCnt, ansCnt) {
                ans = right - winLen + 1
                break
            }
        }
    }

    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(n1+n2)。滑窗过程需要遍历整个s2字符串，初始化需要遍历整个s1字符串。check()函数的时间复杂度最大为O(26)。故整体时间复杂度为O(26(n1+n2)) = O(n1+n2)

空间复杂度：O(1)。win_cnt和ans_cnt哈希表所占空间，由于只包含小写字符串，这两个哈希表所占空间最多为O(26) = O(1)

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

  • 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1441或了解更多

# java # c++ # c语言 # leetcode # javascript # python
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

avatar AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

avatar AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError

avatar AI Agent技术社区