#include <bits/stdc++.h>
using namespace std;
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg];
string s;
double dp[(1<<mxg)],res[(1<<mxg)][mxn],z=1,sum[(1<<mxg)],num[mxg],rsum[(1<<mxg)],zz=2;
double c(double x){
return x/zz;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s;
n=s.size();
for(int i=0;i<n;i++){
int x=s[i];
a[x]=(a[x]==0)?++cnt:a[x];
x=a[x];
all[x]+=z;
for(int j=0;j<(1<<mxg);j++){
if(j&(1<<(x-1))){
rsum[j]+=z;
}
}
}
for(int i=0;i<n;i++){
int x=s[i];
x=a[x];
for(int j=0;j<(1<<cnt);j++){
if(j&(1<<(x-1)))continue;
res[j][x]+=min(sum[j]+c(num[x]),rsum[j]+c(all[x]-num[x]-z));
}
for(int j=0;j<(1<<cnt);j++){
if(j&(1<<(x-1))){
rsum[j]-=z;
sum[j]+=z;
}
}
num[x]+=z;
}
for(int i=1;i<(1<<cnt);i++){
dp[i]=(double)1e18;
for(int j=0;j<cnt;j++){
if(i&(1<<j)){
int y=i-(1<<j);
dp[i]=min(dp[i],dp[y]+res[y][j+1]);
}
}
}
cout<<dp[(1<<cnt)-1];
return 0;
}
Compilation message
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
