acwing-4261

题意

给定一串字符串，求其中有多少长度>=3子串，且该子串中某个字符只出现一次。

思路

最终答案的求取可以通过遍历以i位置为所要求的只出现一次的字符所对应的子串数量来求取。

然后显然我们不可能直接对于每个字符c，都暴力的去找左边有多少个相邻的连续的连续的字符与c不同，以及右边有多少个相邻的连续的连续的字符与c不同。于是，我们需要通过预处理，来记录每个字符左右两边分别有多少个相邻的、连续的、与此字符不同的字符，最终的答案也可以理解为左边挑，右边取，然后相乘即可。假设左边的个数为l，右边的个数为r。那么对于该字符，它的贡献为:

$$ans=\begin{cases}l+r,\text{if $l$=0||$r$=0 }\\ l*r,\text{else } \end{cases}$$

由于还有一个限制是长度>=3，所以对某一边没有符合要求的字符时，需要另一边减去只取一个字符的情况，即：

$$ans=\begin{cases}l+r-1,\text{if ($l$=0||$r$=0)\&\&(l+r>=2) }\\ l*r+(r-1)_{\text{if $r$>=2}}+(l-1)_{\text{if $l$>=2}},\text{else } \end{cases}$$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    str=' '+str;
    vector<int>l(n+2),r(n+2);
    int sum=0;
    for(int i=1;i<=n;++i){
        if(str[i]==str[i-1]){
            l[i]=0;
            sum++;
        }else {
            l[i]=sum;
            sum=1;
        }
    }
    sum=0;
    for(int i=n;i>=1;--i){
        if(str[i]==str[i+1]){
            r[i]=0;
            sum++;
        }else {
            r[i]=sum;
            sum=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        // cerr<<l[i]<<" "<<r[i]<<endl;
        if(l[i]==0||r[i]==0){
            if(l[i]+r[i]>=2)ans+=l[i]+r[i]-1;
        }else {
            ans+=l[i]*r[i];
            if(r[i]>=2)ans+=r[i]-1;
            if(l[i]>=2)ans+=l[i]-1;
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}