[ABC329C] Count xxx 题解
题目分析
目的：统计本质不同而不是位置不同的所有字符都相同的字串。
需要理解一下什么是本质不同而不是位置不同。结合样例1去理解这句话。
列举样例1中的所有所有组成字符相同的字串。
aaabaa
| 编号 | 字串 | 位置 |
|---|---|---|
| \(1\) | a |
\([1,1]\) |
| \(2\) | aa |
\([1,2]\) |
| \(3\) | aaa |
\([1,3]\) |
| \(4\) | b |
\([4,4]\) |
| \(5\) | a |
\([5,5]\) |
| \(6\) | aa |
\([6,7]\) |
其中，编号 \(1\) 与编号 \(5\)，编号 \(2\) 与编号 \(6\) 都属于本质相同的字串。所以，所有位置不同的、组成内容相同的字串，最终只需要保留最长的那一个就好。对于一个长度为 \(k\) 的组成内容相同的字串来说， 存在长度为 \(1,2,\dots,k\) 的本质不同的字串，个数即它的长度。
最终，问题即可理解为求出所有字符构成的最长连号长度的总和。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using i64 = long long;
int n;
char c[N];
int maxL[30];//maxL[i]:字母(i+'a')对应的最长连号长度
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int len = 0;
for (int i = 1; i <= n; i++) {
cin >> c[i];
if (c[i] == c[i - 1]) {//当前元素与前一个元素相同
len++;//连号长度增加
} else {
len = 1;//不同时，开始新的连号
}
//更新当前元素对应的最长连号长度
maxL[c[i]-'a'] = max(maxL[c[i]-'a'], len);
}
//本质不同的串就是最长连号的长度
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += maxL[i];//累加所有元素的最长连号长度
}
cout << ans;
return 0;
}