【大厂机试题+算法可视化】最长的指定瑕疵度的元音子串

题目

开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:
· “a” 、 “aa”是元音字符串，其瑕疵度都为0
· “aiur”不是元音字符串（结尾不是元音字符）
· “abira”是元音字符串，其瑕疵度为2
给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。
子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。

输入描述：
首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。
接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。
输出描述：
输出为一个整数，代表满足条件的元音字符子串的长度。

用例

输入	输出	说明
0 asdbuiodevauufgh	3	满足条件的最长元音字符子串有两个，分别为uio和auu，长度为3
2 aeueo	0	没有满足条件的元音字符子串，输出0
1 aabeebuu	5	满足条件的最长元音字符子串有两个，分别为aabee和eebuu，长度为5

思考一（暴力解法）

找子串问题，暴力解法比较简单，两重循环，第一重循环枚举元音字符作为子串的第一个字符，第二重循环枚举字符作为子串的最后一个字符，并统计这个子串包含的瑕疵度是否满足要求，满足要求计算子串长度，更新最大子串长度。

算法过程

1. 首先读取输入的瑕疵度和字符串；

2. 使用两层循环遍历所有可能的子串；

3. 外层循环找到每个元音字符作为子串的开始；

4. 内层循环从开始位置向后扩展，统计瑕疵度并检查结尾字符是否为元音；

5. 当瑕疵度等于目标值且结尾为元音时，更新最大长度；

6. 最后输出满足条件的最长子串长度。时间复杂度O (n²)。

参考代码

function solution() {const n = parseInt(readline());const s = readline();const set = new Set('aeiouAEIOU'.split(''));let maxLength = 0;for (let i = 0; i < s.length; i++) {if (!set.has(s[i])) continue;let currentFlaw = 0;for (let j = i; j < s.length; j++) {if (!set.has(s[j])) {currentFlaw++;}if (currentFlaw === n && set.has(s[j])) {maxLength = Math.max(maxLength, j - i + 1);}}}console.log(maxLength);
}const cases = [`0
asdbuiodevauufgh`,
`2
aeueo`,
`1
aabeebuu`
];
let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});

思考二（滑动窗口）

包含指定瑕疵度的最长元音子串，子串不是子序列，子串是连续的，所以应该能用滑动窗口解答，用左右两个指针维持一个变动的窗口，这个窗口就是子串，目标是让窗口从左到右滑动覆盖整个字符串，每次窗口变动时都统计瑕疵度，更新全局满足条件的最大窗口，即最大元音子串。此题类似LeetCode 76.最小覆盖子串。
 

算法过程

1. 预处理元音位置：遍历字符串，记录所有元音字符的位置，形成一个元音索引数组。

2. 维护滑动窗口：在元音索引数组上使用滑动窗口，确保窗口内的瑕疵度恰好等于目标值。

3. 快速计算窗口内瑕疵度：通过前缀和数组在 O (1) 时间内获取窗口内的瑕疵度。

滑动窗口策略关键点

1. 窗口定义：窗口左右边界在元音索引数组上移动，而非原字符串。

2. 瑕疵度计算：利用前缀和数组 O (1) 计算窗口内的瑕疵度。

3. 窗口调整：

   • 右边界扩展增加瑕疵度

   • 左边界收缩减少瑕疵度

   • 当瑕疵度恰好等于目标值时记录最大长度

复杂度分析

• 时间复杂度：O (n + m)，其中 n 是原字符串长度，m 是元音字符数量。预处理 O (n)，滑动窗口遍历 O (m)。

• 空间复杂度：O (n + m)，主要用于存储前缀和数组和元音索引数组。

参考代码

function solution() {const n = parseInt(readline());const str = readline();const set = new Set('aeiouAEIOU'.split(''));const vowelIndices = [];const nonVowelCount = [];let count = 0;for (let i = 0; i < str.length; i++) {if (!set.has(str[i])) {count++;}nonVowelCount.push(count); // 记录每个字符位置对应的瑕疵度前缀和if (set.has(str[i])) {vowelIndices.push(i); // 添加元音索引}}const len = vowelIndices.length;if (len === 0) return 0;let maxLen = 0;let l = 0;for (let r = 0; r < len; r++) {// 计算当前窗口[left, right]内的瑕疵度const startIdx = vowelIndices[l];const endIdx = vowelIndices[r];let currentFlaw = nonVowelCount[endIdx] - (startIdx > 0 ? nonVowelCount[startIdx - 1] : 0);// 收缩窗口直到瑕疵度符合要求while (l <= r && currentFlaw > n) {l++;if (l > r) break;const newStartIdx = vowelIndices[l];currentFlaw = nonVowelCount[endIdx] - (newStartIdx > 0 ? nonVowelCount[newStartIdx - 1] : 0);}// 检查当前窗口是否符合条件if (currentFlaw === n) {const length = endIdx - vowelIndices[l] + 1;maxLen = Math.max(maxLen, length);}}console.log(maxLen);
}const cases = [`0
asdbuiodevauufgh`,
`2
aeueo`,
`1
aabeebuu`
];
let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});