[ABC329C] Count xxx 题解

发布时间 2023-11-24 19:40:18作者: gsczl71

插曲

因为本人看错了题面,买看到一个子串包含一种字母,所以切完 D 和 E 才回来发现很简单。

问题翻译

给你一个长度为 \(N\) 的字符串 \(S\),由小写英文字母组成。

\(S\) 的非空子串中有多少个是一个字符的重复。在这里,作为字符串的两个子串是相等的,即使它们是以不同的方式得到的,也加以区分。

\(S\) 的非空子串是通过删除 \(S\) 开头的零个或多个字符和结尾的零个或多个字符得到的长度至少为一个的字符串。例如,ababcabc 的非空子串,而 ac 和空字符串则不是。

分析

如果有一个字符串 AAABAA,那么 AAA 这个子串会重复计算过。所以我们只需要计算每一个字符最长的连续长度。

于是我们可以开一个 \(ans\) 数组,然后维护这每一个字符的最长连续长度,最终答案就是 \(ans\) 数组中的和即可。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define se second
#define endl '\n'
#define debug puts("AK IOI")
using namespace std;
int n;
string s;
int ans[30];
int main(){
	cin >> n >> s;
	s=' '+s;
	int res=0;
	for(int i = 1;i <= n;i++){
		if(s[i] != s[i-1]){
			res=0;
		}res++;
		ans[s[i]-'a'] = max(ans[s[i]-'a'],res);
	}
	int cnt=0;
	for(int i=0;i <=26;i++){
		cnt+=ans[i];
	}cout<<cnt;
	return 0;
}