2023年华为OD机考真题：最左侧冗余覆盖子串

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：最左侧冗余覆盖子串
知识点：滑动窗口
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定2个字符串s1和s2和正整数k，其中s1长度为n1，s2长度为n2，在s2中选一个子串，满足：
该子串长度为n1+k
该子串包含s1中全部字母
该子串每个字母的出现次数不小于s1中对应的字母
我们称s2以长度k冗余覆盖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
示例1
输入：
ab
aabcd
1
输出：
0
说明：
子串aab和abc满足要求，由于aab在abc的左侧，因此输出aab的下下标：0
示例2
输入：
abc
dfs
10
输出：
-1
说明：
s2无法覆盖s1，输出-1
解题思路：
通过s1的长度和k值计算出父字符串的长度
从s2遍历中截取步骤1的长度的字符串作为父字符串
通过双层for循环，求出s1是否为步骤2中的子串
代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最左侧冗余覆盖子串
 * @Description 给定2个字符串s1和s2和正整数k，其中s1长度为n1，s2长度为n2，在s2中选一个子串，满足：
 * 该子串长度为n1+k
 * 该子串包含s1中全部字母
 * 该子串每个字母的出现次数不小于s1中对应的字母
 * 我们称s2以长度k冗余覆盖s1。给定s1、s2和k，求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标，如果没有返回-1
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n1 = sc.nextLine();
        String n2 = sc.nextLine();
        int k = sc.nextInt();
        int res = -1;
        int strLen = n1.length() + k;
        for (int i = 0; i < n2.length() - strLen + 1; i++) {
            char[] chars = n2.substring(i, i + strLen).toCharArray();
            if (qiuzichuan(n1, chars)) {
                res = i;
                break;
            }
        }
        System.out.println(res);
    }

    public static boolean qiuzichuan(String s1, char[] chars) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < chars.length; j++) {
                if (s1.charAt(i) == chars[j]) {
                    chars[j] = ' ';
                    count++;
                    break;
                }
            }
        }
        return count == s1.length();
    }

}

代码实现二：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最左侧冗余覆盖子串
 * @Description 给定2个字符串s1和s2和正整数k，其中s1长度为n1，s2长度为n2，在s2中选一个子串，满足：
 * 该子串长度为n1+k
 * 该子串包含s1中全部字母
 * 该子串每个字母的出现次数不小于s1中对应的字母
 * 我们称s2以长度k冗余覆盖s1。给定s1、s2和k，求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标，如果没有返回-1
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int n1 = s1.length(); // 0 <= n1 <= 1000000
        int n2 = s2.length(); // 0 <= n2 <= 20000000
        int k = in.nextInt(); // 冗余 0 <= k <= 1000
        int subLen = n1 + k; // 子串长度
        // s2长度不满足冗余长度
        if (n2 < subLen) {
            System.out.print("-1");
            return;
        }
        // 记录子串中26个字母出现的次数
        int[] charCountArr = new int[26];
        // 用最左子串初始化
        String sub0 = s2.substring(0, 0 + subLen);
        for (char c : sub0.toCharArray()) {
            charCountArr[c - 'a']++;
        }
        int[] charArrS1 = new int[26];
        for (char c : s1.toCharArray()) {
            charArrS1[c - 'a']++;
        }
        // 从最左侧遍历，遇到一个满足条件的子串即可
        int firstChar = s2.charAt(0);
        for (int i = 0; i <= n2 - subLen; i++) {
            char newChar = s2.charAt(i + subLen - 1);
            if (i > 0) {
                // 每次取新的子串，就将字符数组更新
                charCountArr[firstChar - 'a']--;
                charCountArr[newChar - 'a']++;
                firstChar = s2.charAt(i);
            }

            if (canCover(charCountArr, charArrS1)) {
                System.out.print(i);
                return;
            }
        }
        // 遍历完都没有找到满足条件的子串
        System.out.print("-1");
        return;
    }

    // arr 中每个字母出现的次数，不小于 s1 中对应字母出现的次数，就可以覆盖
    public static boolean canCover(int[] arr, int[] s1) {
        for (int i = 0; i < 26; i++) {
            if (arr[i] < s1[i]) {
                return false;
            }
        }
        // 遍历完成，说明成功覆盖
        return true;
    }
}