华为OD机考 2025C卷 - 最左侧冗余覆盖子串 (C++ & Python & JAVA & JS & GO)

最左侧冗余覆盖子串

华为OD机试真题目录点击查看: 华为OD机试2025C卷真题题库目录｜机考题库 + 算法考点详解

华为OD机试 2025C卷 100分题型

题目描述

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

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

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

输入描述

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

备注

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

输出描述

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

示例1

输入

ab
aabcd
1

输出

0

说明

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

示例2

输入

abc
dfs
10

输出

-1

说明

s2无法覆盖s1，输出 -1

题解

思路：题解涉及算法滑动窗口，窗口大小为s1.length + k

• 使用remainingMatches 保存待匹配的字符数量。使用patternFreq统计s1中各个字母的出现的数量。使用windowFreq统计s2位于窗口中各个字母的出现的数量。
• 具体执行过程一下：当窗口右移时
  • 右边界右移(right++)，增加windowFreq[rightChar – 'a']++;, 当windowFreq[rightChar – 'a'] <= patternFreq[rightChar – 'a']时，remainingMatches –.
  • 左边界右移之前，判断windowFreq[leftChar – 'a'] <= patternFreq[leftChar – 'a']如果成立,remainingMatches++, windowFreq[leftChar – 'a']–,left++
• 在窗口移动过程，存在remainingMatches = 0 时，既满足条件，输出这时的left既是结果。

c++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
string pattern, text;
getline(cin, pattern); // 读取模式串
getline(cin, text); // 读取目标文本
int maxExtraChars;
cin >> maxExtraChars; // 允许的额外字符数

int startIndex = –1;
vector<int> patternFreq(26, 0); // 记录 pattern 中每个字符的出现次数
for (char c : pattern) {
patternFreq[c – 'a']++;
}

int left = 0, right = 0;
// 待需要匹配字符数量
int remainingMatches = pattern.length();
vector<int> windowFreq(26, 0); // 记录滑动窗口中的字符出现次数

while (right < text.length()) {
char rightChar = text[right];
windowFreq[rightChar – 'a']++;

if (windowFreq[rightChar – 'a'] <= patternFreq[rightChar – 'a']) {
remainingMatches—;
}

if (right – left + 1 > pattern.length() + maxExtraChars) {
char leftChar = text[left];
if (windowFreq[leftChar – 'a'] <= patternFreq[leftChar – 'a']) {
remainingMatches++;
}
windowFreq[leftChar – 'a']—;
left++;
}

if (remainingMatches == 0) {
startIndex = left;
break;
}

right++;
}

cout << startIndex;
return 0;
}

Java

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

// 读取模式串
String pattern = scanner.nextLine();
// 读取目标文本
String text = scanner.nextLine();
// 允许的额外字符数
int maxExtraChars = scanner.nextInt();
scanner.close();

int startIndex = –1;
int[] patternFreq = new int[26]; // 记录 pattern 中每个字符的出现次数
for (char c : pattern.toCharArray()) {
patternFreq[c – 'a']++;
}

int left = 0, right = 0;
int remainingMatches = pattern.length(); // 待匹配字符数量
int[] windowFreq = new int[26]; // 记录滑动窗口中的字符出现次数

while (right < text.length()) {
char rightChar = text.charAt(right);
windowFreq[rightChar – 'a']++;

if (windowFreq[rightChar – 'a'] <= patternFreq[rightChar – 'a']) {
remainingMatches—;
}

if (right – left + 1 > pattern.length() + maxExtraChars) {
char leftChar = text.charAt(left);
if (windowFreq[leftChar – 'a'] <= patternFreq[leftChar – 'a']) {
remainingMatches++;
}
windowFreq[leftChar – 'a']—;
left++;
}

if (remainingMatches == 0) {
startIndex = left;
break;
}

right++;
}

System.out.println(startIndex);
}
}

Python

import sys

# 读取模式串
pattern = sys.stdin.readline().strip()
# 读取目标文本
text = sys.stdin.readline().strip()
# 允许的额外字符数
max_extra_chars = int(sys.stdin.readline().strip())

pattern_freq = [0] * 26 # 记录 pattern 中每个字符的出现次数
for c in pattern:
pattern_freq[ord(c) – ord('a')] += 1

left, right = 0, 0
remaining_matches = len(pattern) # 待匹配字符数量
window_freq = [0] * 26 # 记录滑动窗口中的字符出现次数
start_index = –1

while right < len(text):
right_char = text[right]
window_freq[ord(right_char) – ord('a')] += 1

if window_freq[ord(right_char) – ord('a')] <= pattern_freq[ord(right_char) – ord('a')]:
remaining_matches -= 1

if right – left + 1 > len(pattern) + max_extra_chars:
left_char = text[left]
if window_freq[ord(left_char) – ord('a')] <= pattern_freq[ord(left_char) – ord('a')]:
remaining_matches += 1
window_freq[ord(left_char) – ord('a')] -= 1
left += 1

if remaining_matches == 0:
start_index = left
break

right += 1

print(start_index)

JavaScript

const readline = require('readline');

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

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

rl.on('close', () => {
let pattern = inputLines[0]; // 读取模式串
let text = inputLines[1]; // 读取目标文本
let maxExtraChars = parseInt(inputLines[2]); // 允许的额外字符数

let patternFreq = Array(26).fill(0); // 记录 pattern 中每个字符的出现次数
for (let c of pattern) {
patternFreq[c.charCodeAt(0) – 'a'.charCodeAt(0)]++;
}

let left = 0, right = 0, remainingMatches = pattern.length;
let windowFreq = Array(26).fill(0); // 记录滑动窗口中的字符出现次数
let startIndex = –1;

while (right < text.length) {
let rightChar = text[right];
windowFreq[rightChar.charCodeAt(0) – 'a'.charCodeAt(0)]++;

if (windowFreq[rightChar.charCodeAt(0) – 'a'.charCodeAt(0)] <= patternFreq[rightChar.charCodeAt(0) – 'a'.charCodeAt(0)]) {
remainingMatches—;
}

if (right – left + 1 > pattern.length + maxExtraChars) {
let leftChar = text[left];
if (windowFreq[leftChar.charCodeAt(0) – 'a'.charCodeAt(0)] <= patternFreq[leftChar.charCodeAt(0) – 'a'.charCodeAt(0)]) {
remainingMatches++;
}
windowFreq[leftChar.charCodeAt(0) – 'a'.charCodeAt(0)]—;
left++;
}

if (remainingMatches === 0) {
startIndex = left;
break;
}

right++;
}

console.log(startIndex);
});

Go

package main

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

func main() {
// 使用 bufio.Scanner 读取大数据
scanner := bufio.NewScanner(os.Stdin)

// 读取模式串
scanner.Scan()
pattern := scanner.Text()

// 读取目标文本
scanner.Scan()
text := scanner.Text()

// 读取允许的额外字符数 k
scanner.Scan()
maxExtraChars, _ := strconv.Atoi(scanner.Text())

// 记录 pattern 中每个字符的出现次数
patternFreq := make([]int, 26)
for _, c := range pattern {
patternFreq[c–'a']++
}

left, right := 0, 0
remainingMatches := len(pattern) // 待匹配字符数量
windowFreq := make([]int, 26) // 记录滑动窗口中的字符出现次数
startIndex := –1

for right < len(text) {
rightChar := text[right]
windowFreq[rightChar–'a']++

if windowFreq[rightChar–'a'] <= patternFreq[rightChar–'a'] {
remainingMatches—
}

if right–left+1 > len(pattern)+maxExtraChars {
leftChar := text[left]
if windowFreq[leftChar–'a'] <= patternFreq[leftChar–'a'] {
remainingMatches++
}
windowFreq[leftChar–'a']—
left++
}

if remainingMatches == 0 {
startIndex = left
break
}

right++
}

fmt.Println(startIndex)
}