Polycarp Writes a String from Memory CodeForces - 1702B

Polycarp Writes a String from Memory CodeForces - 1702B

给定大小为 n 的字符串，至多每 3 种不同的字母分为一组，最少将字符串分为多少组？

Input

第一行输入数据包含一个整数 t（1≤t≤1e4）-测试用例的数量。
每个测试用例都包含一个非空字符串s，由小写拉丁字母组成（字符串s的长度不超过2e5）。
保证所有测试用例中的字符串长度s之和不超过2e5。

Output

对于每个测试用例，打印一个数字，从内存中写入字符串所需的最少天数。

Sample Input

6
lollipops
stringology
abracadabra
codeforces
test
f

Sample Output

2
4
3
4
1
1

分析

直接模拟，开个标记数组，记录是否出现过该元素。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
char a[N];

int main(){
    // freopen("data.in", "r", stdin);
    int t; scanf("%d", &t);
    while(t--){
        scanf("%s", a);
        int n=strlen(a), vis[26]={0}, p=0, ans=0;
        for(int i=0; i<n; i++){
            if(!vis[a[i]-'a']) vis[a[i]-'a']=1, p++;
            if(p%3==0){
                ans++; int j=i+1;
                while(j<n && vis[a[j]-'a']) j++;
                if(j != i+1) i = j-1;
                memset(vis, 0, sizeof(vis));
            }
        }
        if(p%3!=0) ans++;
        printf("%d\n", ans);
    }
    return 0;
}