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

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

开头和结尾都是元音字母（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。

瑕疵度表： 非元音字母的数量。

元音字符下标：维护元音字符下标位置，后续通过双指针方式去遍历元音下标更高效。

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

解题思路:

遍历字符串，将元音字符的下标存储起来。

使用滑动窗口，维护左右指针，计算窗口内的瑕疵度。

如果当前窗口的瑕疵度大于预期瑕疵度，则移动左指针，缩小窗口；否则，更新最长元音字符子串的长度。

最终输出最长元音字符子串的长度。

代码解释:

使用一个瑕疵度表 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 < vowelIdxs.size(); r++) {
            int right = vowelIdxs.get(r);
            while (l <= r) {
                int left = vowelIdxs.get(l);
                // 计算区间内的瑕疵度
                int curFlaw = flawCnt[right + 1] - flawCnt[left];
                if (curFlaw > flaw) { // 比预期的瑕疵度大，则左侧指针右移缩小窗口
                    l++;
                    continue;
                }
                if (curFlaw == flaw) max_length = Math.max(max_length, right - left + 1);
                break;
            }
        }

        System.out.println(max_length);
    }
}

Python

import string

def solve(flaw: int, s: string) -> int:
    """找出指定瑕疵度的最长元音字符子串，并返回其长度"""
    n = len(s)
    flaw_cnt = [0] * (n + 1)    # 瑕疵度表, flaw_cnt[x] 表示前 s[:x] 的瑕疵度
    vowels = set("aeiouAEIOU")
    vowel_idxs = []             # 元音字符下标列表

    cnt = 0
    for i, c in enumerate(s):
        if c in vowels:  # 元音字符
            vowel_idxs.append(i)
        else:  # 非元音字母:  瑕疵度 + 1
            cnt += 1
        flaw_cnt[i + 1] = cnt

    l, max_length = 0, 0
    for r in range(len(vowel_idxs)):
        right = vowel_idxs[r]
        while l <= r:
            left = vowel_idxs[l]
            # 计算区间内的瑕疵度
            cur_flaw = flaw_cnt[right + 1] - flaw_cnt[left]
            if cur_flaw > flaw:  # 比预期的瑕疵度大，则左侧指针右移缩小窗口
                l += 1
                continue
            if cur_flaw == flaw:
                max_length = max(max_length, right - left + 1)
            break

    return max_length


if __name__ == "__main__":
    flaw = int(input())
    s = input()
    print(solve(flaw, s))

C++

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int solve(int flaw, const string& s) {
    int n = s.length();
    vector<int> flaw_cnt(n + 1, 0); // 瑕疵度表，flaw_cnt[x] 表示前 s[:x] 的瑕疵度
    unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
    vector<int> vowel_idxs; // 元音字符下标列表

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (vowels.count(c)) { // 元音字符
            vowel_idxs.push_back(i);
        } else { // 非元音字母：瑕疵度 + 1
            cnt++;
        }
        flaw_cnt[i + 1] = cnt;
    }

    int max_length = 0;
    size_t l = 0;
    for (size_t r = 0; r < vowel_idxs.size(); r++) {
        int right = vowel_idxs[r];
        while (l <= r) {
            int left = vowel_idxs[l];
            // 计算区间内的瑕疵度
            int cur_flaw = flaw_cnt[right + 1] - flaw_cnt[left];
            if (cur_flaw > flaw) { // 比预期的瑕疵度大，则左侧指针右移缩小窗口
                l++;
                continue;
            }
            if (cur_flaw == flaw) max_length = max(max_length, right - left + 1);
            break;
        }
    }

    return max_length;
}

int main() {
    int flaw;
    cin >> flaw;
    string s;
    cin >> s;
    cout << solve(flaw, s) << endl;

    return 0;
}

🙏整理题解不易，如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏

#面经##春招##校招##秋招##华为#