题目描述
难度分:1700
输入长度≤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种情况:
- 纯元音
AEIOU
,设频数为cnt0; - 字母
N
,设频数为ncnt; - 字母
G
,设频数为gcnt; - 字母
Y
,设频数为ycnt; - 除了上述字母之外的纯辅音字母,设频数为cnt1。
枚举长度为5的音节数量cnt5∈[cnt0+ycnt,min(gcnt,ncnt)2],由于Y
可以作为辅音也可以作为元音,所以先消耗纯元音去构造长度为5的音节,如果纯元音消耗完了再消耗Y
。
在固定cnt5的情况下,枚举长度为4的音节数量cnt4∈[cnt0+ycnt,min(gcnt,ncnt)],其中cnt0、ycnt、gcnt、ncnt都是构造完长度为5的音节之后剩下的纯元音、Y
、G
、N
、纯辅音频数,后续相同的字母都是如此,不再赘述,但在实现的时候注意缓存,不要用同一个变量。同样由于Y
可以作为元音也可以作为辅音,先消耗纯元音,消耗完了再消耗Y
。
在固定cnt5和cnt4的情况下,枚举剩余的Y
有vcnt个看作元音。这样就能计算出长度为3的音节有多少个,假设为cnt3。维护cnt5×5+cnt4×4+cnt3×3的最大值,这个最大值就是答案。
复杂度分析
时间复杂度
枚举cnt5和cnt4的时候虽然是双重循环,但两者都需要用到NG
,相互限制,此消彼长,cnt5用得多cnt4就用得少,cnt5用得少cnt4就用得多。本质上是在消耗除了纯辅音之外的字母,量级可以是O(n)。最内层需要根据Y
的余量进一步枚举多少个Y
作为元音,在最差情况下Y
完全没有消耗,因此枚举元音Y
的时间复杂度也是O(n)。整个算法的时间复杂度为O(n2)。
空间复杂度
除了输入的字符串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;
}