C++ 解法, 执行用时: 4ms, 内存消耗: 800K, 提交时间: 2023-08-12 11:24:06

#include <bits/stdc++.h>
using namespace std;
string s;
int last[100005],nxt[100005];
int pos[26];
int main(){
    cin>>s;
    int n=s.size();
    for(int i=0;i<26;i++)pos[i]=-1;
    for(int i=0;i<n;i++){
        last[i]=pos[s[i]-'a'];
        pos[s[i]-'a']=i;
    }
    for(int i=0;i<26;i++)pos[i]=n;
    for(int i=n-1;i>=0;i--){
        nxt[i]=pos[s[i]-'a'];
        pos[s[i]-'a']=i;
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        ans+=(i-last[i])*(nxt[i]-i);
    }
    cout<<ans<<endl;
    return 0;
}

Python3 解法, 执行用时: 420ms, 内存消耗: 25196K, 提交时间: 2023-08-12 11:23:44

A=[[0 for j in range(100010)]for i in range(26)] 
s=input().strip()
length=len(s)+1
for i in range(1,length):A[ord(s[i-1])-97][i]=1
for i in range(26):A[i][0]=A[i][length]=1
cnt=0
for i in range(26):
    head=mid=tail=0
    for j in range(1,length+1):
        if A[i][j]:
            if mid:
                tail=j
                cnt+=(tail-mid)*(mid-head)
                head=mid
                mid=tail
            else:
                mid=j
print(cnt)