最长的指定瑕疵度的元音字串 —— 最优解法（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
           

解题思路

一般思考这种字串之类的题目，都可以从最少遍历次数的角度去考虑最优解。多次的冗余计算并不是我追求的目标。

在这道题目中，有这样一种思路是满足要求的。两个指针fp，bp，都从头开始，fp先找到指定的flaw个瑕疵字符，接着向后找到最后一个元音字符。此时fp，bp锁囊括的就是一个解。接着，两个指针同时向后遍历，找到所有满足的字符串。这样算下来，只需要遍历两次，就可以完全算出来。

这样可以实现，但是，我又想到了更好的方法。

idea：假定元音字符是A类字符，非元音字符为B类字符，同类型的具体是什么字符是不是没有关系。所以，我们可以将同类字符合并。如 aabeebuu 就可以用 {2,1,2,1,2}的数组去保存。我们的目的，也变为了，找到这个数组中连续几个数值的最大，且下标为奇数的和等于flaw。

下面上代码。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

bool is_aeiou(char c) {
    static std::string aeiou = "aeiouAEIOU";
    return std::string::npos != aeiou.find(c);
}

int find_max_length(const std::string & str, int flaw) {
    if (str.size() == 0)
        return 0;

    std::vector<int> sums;

    bool tmp = true;    // 第一个字符一定是元音字符，输入已保证
    int k = 0;
    for (auto c : str) {
        if (tmp == is_aeiou(c)) {
            k++;
        } else {
            sums.push_back(k);
            tmp = is_aeiou(c);
            k = 1;
        }
    }

    sums.push_back(k);

    int head = 0;
    int tail = 0;

    int tt = 0;
    int length = 0;
    while (tail < sums.size() - 1) {
        // 特殊情况：tail已经为最后一个
        while (tt < flaw && tail < sums.size() - 1) {
            tail += 2;
            tt += sums[tail-1];
        }
     
        while (tt > flaw) {
            head += 2;
            tt -= sums[head-1];
        }
        // 特殊情况，flaw为0，对比所有元音串的长度
        if (flaw == 0) {
            length = length > sums[tail] ? length : sums[tail];
            tail += 2;
            if (tail == tail < sums.size() - 1)
                length = length > sums[tail] ? length : sums[tail];
        }
        // 先加后减，只有正好的时候，才纳入计算
        else if (tt == flaw) {
            int ss = (std::accumulate(sums.begin() + head, sums.begin() + tail + 1, 0));
            length = length > ss ? length : ss;
            head += 2;
            tt -= sums[head-1];
        }
    }
    return length;
}
 
int main()
{
    // std::cout << find_max_length("asdbuiodevauufgh", 0) << std::endl;
    // std::cout << find_max_length("aeueo", 2) << std::endl;
    std::cout << find_max_length("aabeebuu", 1) << std::endl;
}