题目描述

难度分:$1700$

输入长度$\leq 5000$的字符串$s$，只包含大写英文字母。

字母AEIOU是元音。Y可以是元音也可以是辅音。
其余字母为辅音。特别地，可以把NG连在一起，当作一个辅音。

定义音节为一个辅音$+$一个元音$+$一个辅音。例如CAR，KING 等等。

定义单词为由一个或多个音节串联得到的字符串。例如KINGDOM是由 KING$+$DOM两个音节组成。

从$s$中删除零个或多个字母，然后重新排列剩余的字母，组成单词。

输出最长单词长度。如果无法组成单词，输出$0$。

输入样例$1$

ICPCJAKARTA

输出样例$1$

9

输入样例$2$

NGENG

输出样例$2$

5

输入样例$3$

YYY

输出样例$3$

3

输入样例$4$

DANGAN

输出样例$4$

6

输入样例$5$

AEIOUY

输出样例$5$

0

算法

枚举

本题可以对删除字符后的字符串重排，所以大概率统计出各个字母的频数就能做出来。将所有字母分为$5$种情况：

1. 纯元音AEIOU，设频数为$cnt_0$；
2. 字母N，设频数为$ncnt$；
3. 字母G，设频数为$gcnt$；
4. 字母Y，设频数为$ycnt$；
5. 除了上述字母之外的纯辅音字母，设频数为$cnt_1$。

枚举长度为$5$的音节数量$cnt_5 \in [cnt_0+ycnt,\frac{min(gcnt,ncnt)}{2}]$，由于Y可以作为辅音也可以作为元音，所以先消耗纯元音去构造长度为$5$的音节，如果纯元音消耗完了再消耗Y。

在固定$cnt_5$的情况下，枚举长度为$4$的音节数量$cnt_4 \in [cnt_0+ycnt,min(gcnt,ncnt)]$，其中$cnt_0$、$ycnt$、$gcnt$、$ncnt$都是构造完长度为$5$的音节之后剩下的纯元音、Y、G、N、纯辅音频数，后续相同的字母都是如此，不再赘述，但在实现的时候注意缓存，不要用同一个变量。同样由于Y可以作为元音也可以作为辅音，先消耗纯元音，消耗完了再消耗Y。

在固定$cnt_5$和$cnt_4$的情况下，枚举剩余的Y有$vcnt$个看作元音。这样就能计算出长度为$3$的音节有多少个，假设为$cnt_3$。维护$cnt_5 \times 5 + cnt_4 \times 4 + cnt_3 \times 3$的最大值，这个最大值就是答案。

复杂度分析

时间复杂度

枚举$cnt_5$和$cnt_4$的时候虽然是双重循环，但两者都需要用到NG，相互限制，此消彼长，$cnt_5$用得多$cnt_4$就用得少，$cnt_5$用得少$cnt_4$就用得多。本质上是在消耗除了纯辅音之外的字母，量级可以是$O(n)$。最内层需要根据Y的余量进一步枚举多少个Y作为元音，在最差情况下Y完全没有消耗，因此枚举元音Y的时间复杂度也是$O(n)$。整个算法的时间复杂度为$O(n^2)$。

空间复杂度

除了输入的字符串$s$，整个算法过程仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5010;
char s[N];
int n;
unordered_set<char> vowel{'A', 'E', 'I', 'O', 'U'};

void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int cnt0 = 0, cnt1 = 0, ycnt = 0, ncnt = 0, gcnt = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'Y') {
            ycnt++;
        }else if(s[i] == 'N') {
            ncnt++;
        }else if(s[i] == 'G') {
            gcnt++;
        }else {
            if(vowel.count(s[i])) {
                cnt0++;     // 纯元音
            }else {
                cnt1++;     // 纯辅音
            }
        }
    }
    int ans = 0;
    for(int cnt5 = 0; cnt5 <= min(cnt0 + ycnt, min(gcnt, ncnt)/2); cnt5++) {
        // 枚举两侧都是NG的音节个数
        int len = cnt5 * 5;
        int nc = ncnt - cnt5 * 2, gc = gcnt - cnt5 * 2, c1 = cnt1;
        // 因为Y还可以做元音，所以先消耗纯元音
        int c0 = cnt0, y = ycnt;
        if(c0 >= cnt5) {
            c0 -= cnt5;
        }else {
            y -= cnt5 - c0;
            c0 = 0;
        }
        for(int cnt4 = 0; cnt4 <= min(c0 + y, min(nc, gc)); cnt4++) {
            // 枚举一侧是NG的音节个数
            int c0_ = c0, y_ = y;
            // 还是先消耗纯元音
            if(c0_ >= cnt4) {
                c0_ -= cnt4;
            }else {
                y_ -= cnt4 - c0_;
                c0_ = 0;
            }
            int nc_ = nc - cnt4, gc_ = gc - cnt4;
            // 检查辅音够不够
            if(cnt4 <= c1 + nc_ + gc_ + y_) {
                int len_ = len + cnt4 * 4;
                // 先消耗c1+nc_+gc_
                int c11 = 0;     // 纯辅音余量
                if(cnt4 <= c1 + nc_ + gc_) {
                    c11 = c1 + nc_ + gc_ - cnt4;
                }else {
                    y_ -= cnt4 - (c1 + nc_ + gc_);
                }
                for(int vcnt = 0; vcnt <= y_; vcnt++) {
                    // 看用多少个Y当中心
                    int yy = y_;
                    yy -= vcnt;     // 剩下的Y只能作为辅音
                    // 长度为3的音节个数
                    int cnt3 = min(c0_ + vcnt, (c11 + yy) / 2);
                    ans = max(ans, len_ + cnt3 * 3);
                }
            }else {
                break;
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T = 1;
    while(T--) {
        solve();
    }
    return 0;
}