本文共 827 字，大约阅读时间需要 2 分钟。

首先让ans最大组合取ans=n*(n-1)/2.

因为有这样一个字符串，它的每一个字符都属于一个长度大于1的回文子串中

所以回文子串组合，比如长度为5的字符串

最多的子串组合，无非是

s1s2 s1s2s3 s1s2s3s4 s1s2s3s4s5

s2s3 s2s3s4 s2s3s4s5

s3s4 s3s4s5

s4s5

所以最多共有1+2+···+n-1=n*(n-1)/2

然后进行删减，因为只有A,B两个字符，所以对于每一段相同的字母，且满足长度大于1的情况下，用tp记录下当前它的长度，那么顺着遍历和逆着遍历，直到去掉所有不满足条件的子串

Codes

#include
   
    #include
    
     #define ll long longusing namespace std;int main(){
       ll n, ans;    string str;    cin >> n;    cin >> str;    ans = n * (n - 1) / 2;    int tp = 0, tmp = 0;    for (int i = 1; i < n;i++){
           if(str[i-1]!=str[i]){
               ans -= (i - tp);            tp = i;            tmp++;        }    }    ans += tmp;tp = n - 1;    for (int i = n - 2; i >=0;i--){
           if(str[i]!=str[i+1]){
               ans -= (tp - i);            tp = i;        }    }    cout << ans << endl;    return 0;}
    
   

转载地址：http://qdwzi.baihongyu.com/