子串分值复杂解法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

#include<string>

using namespace std;

int leftbound[100000];

int rightbound[100000];

int main(){

    int sum = 0;

    string str;

    cin>>str;

    int len = str.size();

    int arrright[26] = {0};

    int countright[26] = {0};

    for(int j = len-1 ; j >= 0 ; j--){

        int r = str[j]-'a';

        countright[r]++;

        if(countright[r] == 1){

            rightbound[j] = len-j;

        }else{

            rightbound[j] = arrright[r] - j;

        }

        arrright[r] = j;

    }

    int arrleft[26] = {0};

    int countleft[26] = {0};

    for(int i = 0 ; i < len ; i++){

        int l = str[i]-'a';

        countleft[l]++;

        if(countleft[l] == 1){

            leftbound[i] = i + 1;

        }else{

            leftbound[i] = i - arrleft[l];

        }

        arrleft[l] = i;

        sum = sum + leftbound[i] + rightbound[i] - 1 + (leftbound[i]-1)*(rightbound[i]-1);

    }

    cout<<sum<<endl;

    return 0;

}