ABC375D，怎样做到以O(n)的时间复杂度求出一个序列内任意两数差的和？

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+5;
int n,sum;
string s;
int a[30][N],cnt[N];
int dig(char s){
	return s-'A';
}
signed main(){
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++) a[dig(s[i])][++cnt[dig(s[i])]]=i;
	for(int i=0;i<26;i++){
		if(cnt[i]<2) continue;
		for(int j=1;j<cnt[i];j++)
			for(int k=j+1;k<=cnt[i];k++)
				sum+=a[i][k]-a[i][j]-1;
	}
	cout<<sum;
	return 0;
}