最长的指定瑕疵度的元音子串 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:

• “a” 、 “aa” 是元音字符串，其瑕疵度都为0

• “aiur” 不是元音字符串（结尾不是元音字符）

• “abira” 是元音字符串，其瑕疵度为2

给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。

输入描述

首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。

接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。

输出描述

输出为一个整数，代表满足条件的元音字符子串的长度。

示例1

输入：
0
asdbuiodevauufgh

输出：
3

说明：满足条件的最长元音字符子串有两个，分别为uio和auu，长度为3。

示例2

输入：
2
aeueo

输出：
0

说明：没有满足条件的元音字符子串，输出0

示例3

输入：
1
aabeebuu

输出：
5

说明：满足条件的最长元音字符子串有两个，分别为aabee和eebuu，长度为5

题解

题目解析:

题目要求找到指定瑕疵度的最长元音字符子串，并输出其长度。首先，需要定义元音字符和瑕疵度的概念：

• 元音字符： 题目中明确定义为aeiouAEIOU。
• 瑕疵度表： 非元音字母的数量。
• 元音字符下标： 维护元音字符下标位置，后续通过双指针方式去遍历元音下标更高效。

然后，通过滑动窗口的遍历字符串方式，维护一个左指针和右指针。在滑动窗口的过程中，不断调整左右指针，计算当前窗口内的瑕疵度，并判断是否满足预期的瑕疵度。最终，找到满足条件的最长元音字符子串的长度。

解题思路:

1. 遍历字符串，将元音字符的下标存储起来。
2. 使用滑动窗口，维护左右指针，计算窗口内的瑕疵度。
3. 如果当前窗口的瑕疵度大于预期瑕疵度，则移动左指针，缩小窗口；否则，更新最长元音字符子串的长度。
4. 最终输出最长元音字符子串的长度。

代码解释:

• 使用一个瑕疵度表 flawCnt，记录每个位置的瑕疵度。
• 将元音字符的下标存储在 vowelIdxs 列表中。
• 遍历元音字符下标列表，通过滑动窗口计算瑕疵度，更新最长元音字符子串的长度。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int flaw = scanner.nextInt();
        String s = scanner.next();
        int n = s.length();
        int[] flawCnt = new int[n + 1]; // 瑕疵度表，flawCnt[x] 表示前 s[:x] 的瑕疵度
        Set<Character> vowels = "aeiouAEIOU".chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
        List<Integer> vowelIdxs = new ArrayList<>(); // 元音字符下标列表

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (vowels.contains(c)) { // 元音字符
                vowelIdxs.add(i);
            } else { // 非元音字母：瑕疵度 + 1
                cnt++;
            }
            flawCnt[i + 1] = cnt;
        }

        int l = 0, max_length = 0;
        for (int r = 0; r < vow