题解 | #abb#

开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。
按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列满足差后等差，且差后的等差数列公差为1。按照这一性质，即可得到下面的处理方法。
对每一个字符c，从该字符的前一个字符向前遍历，每遇到一个与c相同的字符，count++，每遇到一个与c不同的字符，使sum.at(i)+=count。

这种做法时间复杂度为O(n^2)，比较高。所以在提交后第8个用例处超时，由于用例输入数据过多，无法判断是循环内部逻辑导致超时，还是单纯的时间复杂度过高导致超时。这里暂且认为是时间复杂度过高导致超时，转而寻找时间复杂度更低的做法。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    int n;
    string str;
    cin >> n;
    cin >> str;
    vector<long long> sum(n);
    for(int i = 0;i < n;i++){
        if(i < 2){
            sum.at(i) = 0;
        }
        else{
            int count = 0;
            sum.at(i) = sum.at(i - 1);
            for(int j = i - 1;j > - 1;j--){
                if(str[j] == str[i]){
                    count++;
                }
                else{
                    if(count > 0){
                        sum.at(i) += count; 
                    }
                }
            }
        }
    }
    cout << sum.at(n - 1);
    return 0;
}

参考了别人的做法后发现，维护一个字母出现次数的后缀和数组会更为合理，时间复杂度也更低。
建立一个后缀和数组sum，使sum.at(i).at(j)表示下标i~n-1中字母表第j个字母出现的次数。
有了sum后，就可以根据该数组，来逐个计算字符串中每一个字符与后面字母组成的叠词次数。计算方法如同前面所说，使用组合数的计算公式c(2,N)即可。

这种方法虽然看似使用了二重循环，但由于内层循环的循环次数是固定的常数26，所以时间复杂度为O(n)。由于使用了辅助的后缀和数组，空间复杂度为O(n)。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    int n;
    string str;
    cin >> n;
    cin >> str;
    vector<int> temp(26, 0);
    vector<vector<int>> sum(n, temp);
    long long res = 0;
    sum.at(n - 1).at(str[n - 1] - 'a')++;
    for(int i = n - 2;i > -1;i--){
        for(int j = 0;j < 26;j++){
            sum.at(i).at(j) = sum.at(i + 1).at(j);
        }
        sum.at(i).at(str[i] - 'a')++;
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < 26;j++){
            if(j != str[i] - 'a'){
                res += sum.at(i).at(j) * (sum.at(i).at(j) - 1) / 2;
            }
        }
    }
     cout << res;
    return 0;
}