复杂度O(n)版题解

解题思路:

主要利用前缀和思想，一部分值要减掉，一部分值要加上。

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

int m[27][3];//存值

string s;

int main()

{

    cin>>s;

    int i;

    long long sum=0;

    long long qian=0;

    for(i=0;i<s.length();i++)

    {

        int x=s[i]-'a';

        m[x][0]=i+1;

        qian=qian+(m[x][0]-m[x][1])-(m[x][1]-m[x][2]);

        sum=sum+qian;

        m[x][2]=m[x][1];

        m[x][1]=m[x][0];

    }

    printf("%d\n",sum);

    return 0;

}