变鸡器

Problem Statement

$\hspace{15pt}$在高中物理课堂上，我们都接触过了变鸭器，对此颇有兴趣的小火研制了一款可以处理字符串的变鸡器。
$\hspace{15pt}$变鸡器可以对字符串进行任意次数（可以是零次）的以下操作：选择字符串中任意两个不同字符，将其同时删去，剩余字符按原顺序拼接起来。形式化地，变鸡器选择两个下标 $i, j \left(i \lt j\right)$ 满足 $s_i \neq s_j$，将这两个字符同时删去，剩余字符串拼接在一起得到$s_1s_2\cdots s_{i-1}s_{i+1}\cdots s_{j-1}s_{j+1}\cdots s_n$
$\hspace{15pt}$现在，小火想知道，对于给定的字符串 $s$，他能否通过变鸡器将该字符串变为 $\texttt{“CHICKEN”}$。

Input

$\hspace{15pt}$每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 2\times 10^4\right)$ 代表数据组数，每组测试数据描述如下：
$\hspace{15pt}$第一行输入一个正整数 $n\left(1\leq n\leq 10^5\right)$ 代表输入字符串的长度。
$\hspace{15pt}$第二行输入一个长度为 $n$、仅由大写英文字母构成的字符串 $s$。

$\hspace{15pt}$除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times10^5$。

Output

$\hspace{15pt}$对于每一组测试数据，新起一行。如果可以通过变鸡器将字符串 $s$ 变为 $\texttt{“CHICKEN”}$，输出 $\rm YES$，否则输出 $\rm NO$。

Sample

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


输入
6
7
CHICKEN
9
CHOICKPEN
9
CHIZCKZEN
10
CHIXYZCKEN
11
CZZHIYCXKEN
13
COOOOHICKENZW
输出
 YES YES NO NO YES NO

Solving

由于只能选择两个不同的字符删除，我们只需要在确定字符串s中包含子序列 CHICKEN的情况下使得其余的偶数字符中的所有字符最大重复出现的次数小于一半即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define NINF -0x3f3f3f3f
//#define Single
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 0;
const int M = 0; 
void solve()
{
    int n;
    string s,target = "CHICKEN";
    cin >> n >> s;
    int p=0;
    array<int,26> cnt{0};//用于记录每个多余字符的数量
    for(char c : s)
    {	
        //在识别到所有目标序列chicken中的所有字符之前不会将c计入多余字符数组cnt中
        if(p < target.size() and c == target[p])
        {
            p++;
            continue;
        }
        cnt[c-'A']++;
    }
    //得到所有多余字符中出现次数的最大值
    int mx = *max_element(cnt.begin(),cnt.end());
    //计算所有的多余出现的字符之和
    int sum = accumulate(cnt.begin(),cnt.end(),0);
    //判断条件（有子序列chicken and 重复字符最大值不超过一半 and 剩余字符之和是偶数（可以互相抵消））
    if(p==7 and mx*2<=sum and sum%2==0)
    {
        cout << "YES" << endl;
        return;
    }
    cout << "NO" << endl;

}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;
#ifdef Single
    T = 1;
#else
    cin >> T;
#endif
    while(T--)
    {
        solve();
    }
    return 0;
}