fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5;
  4.  
  5. string s;
  6.  
  7. long long nxt[MaxN];
  8. long long first[30], pos[30], last[30];
  9.  
  10. pair<long long,long long> p[30];
  11.  
  12. void input()
  13. {
  14.     cin >> s;
  15. }
  16. void solve()
  17. {
  18.     long long n = s.size();
  19.  
  20.     s = " " + s;
  21.  
  22.     for(long long c=0; c<26; c++)
  23.     {
  24.         first[c] = n + 1;
  25.         last[c] = 0;
  26.     }
  27.  
  28.     for(long long i=n; i>=1; i--)
  29.     {
  30.         long long c = s[i] - 'a';
  31.  
  32.         nxt[i] = first[c];
  33.         first[c] = i;
  34.     }
  35.  
  36.     for(long long c=0; c<26; c++)
  37.         pos[c] = first[c];
  38.  
  39.     long long ans = 0;
  40.  
  41.     for(long long i=1; i<n; i++)
  42.     {
  43.         long long cur = s[i] - 'a';
  44.  
  45.         last[cur] = i;
  46.  
  47.         if(pos[cur] == i)
  48.             pos[cur] = nxt[i];
  49.  
  50.         long long k = min(i,n-i);
  51.  
  52.         long long cnt = 0;
  53.  
  54.         for(long long c=0; c<26; c++)
  55.         {
  56.             long long lenl = k + 1;
  57.             long long lenr = k + 1;
  58.  
  59.             if(last[c] != 0)
  60.             {
  61.                 long long len = i - last[c] + 1;
  62.  
  63.                 if(len <= k)
  64.                     lenl = len;
  65.             }
  66.  
  67.             if(pos[c] <= n)
  68.             {
  69.                 long long len = pos[c] - i;
  70.  
  71.                 if(len <= k)
  72.                     lenr = len;
  73.             }
  74.  
  75.             if(lenl != lenr)
  76.             {
  77.                 p[cnt] = {
  78.                     min(lenl,lenr),
  79.                     max(lenl,lenr) - 1
  80.                 };
  81.  
  82.                 cnt++;
  83.             }
  84.         }
  85.  
  86.         sort(p,p+cnt);
  87.  
  88.         long long cnt2 = 0;
  89.  
  90.         if(cnt > 0)
  91.         {
  92.             long long l = p[0].first;
  93.             long long r = p[0].second;
  94.  
  95.             for(long long j=1; j<cnt; j++)
  96.             {
  97.                 long long newl = p[j].first;
  98.                 long long newr = p[j].second;
  99.  
  100.                 if(newl > r+1)
  101.                 {
  102.                     cnt2 += r-l+1;
  103.  
  104.                     l = newl;
  105.                     r = newr;
  106.                 }
  107.                 else
  108.                     r = max(r,newr);
  109.             }
  110.  
  111.             cnt2 += r-l+1;
  112.         }
  113.  
  114.         ans += k-cnt2;
  115.     }
  116.  
  117.     cout << ans;
  118. }
  119. int main()
  120. {
  121.     ios_base::sync_with_stdio(0);
  122.     cin.tie(0);
  123.     freopen("file.inp", "r", stdin);
  124.     freopen("file.out", "w", stdout);
  125.     input();
  126.     solve();
  127.  
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LPz3g5
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!