1
int n;
2
string s,ss;
3

4
string manacherss(const string& s){
5
  int n=s.size()*2+1;
6
  string ss;
7
  ss.resize(n);
8
  for(int i=0,j=0;i<n;i++){
9
    ss[i]=(i&1)==0?'#':s[j++];
10
  }
11
  return ss;
12
}
13

14
ll manacher(const string& s){
15
  string ss=manacherss(s);
16
  int ssn=ss.size();
17
  vector<int> dp(ssn,0),b(ssn,0);
18
  for(int i=0,c=0,r=0,len;i<ssn;i++){
19
    len=r>i?min(dp[2*c-i]+1,r-i):1;
20
    while(i+len<ssn&&i-len>=0&&ss[i+len]==ss[i-len]){
21
      len++;
22
    }
23
    if(i+len>r){
24
      r=i+len;
25
      c=i;
26
    }
27
    dp[i]=len-1;
28
  }
29
  ll ans=0;
30
  // 统计一段中只有两种字符的最大长度的左端点
31
  vector<int> dic(26,0);
32
  int cnt=0;
33
  for(int l=0,r=0;r<ssn;r++){
34
    if(ss[r]!='#'){
35
      if(dic[ss[r]-'a']==0){
36
        cnt++;
37
      }
38
      dic[ss[r]-'a']++;
39
    }
40
    while(cnt>2){
41
      if(ss[l]!='#'){
42
        if(dic[ss[l]-'a']==1){
43
          cnt--;
44
        }
45
        dic[ss[l]-'a']--;
46
      }
47
      l++;
48
    }
49
    b[r]=l;
50
  }
51
  int q=0;
52
  for(int i=0;i<ssn;i++){
53
    if(i>0){
54
      q=max(0,q-1);
55
    }
56
    while(i-q-1>=0&&i+q+1<ssn&&b[i+q+1]<=i-q-1){
57
      q++;
58
    }
59
    int r=min(dp[i],q);
60
    ans+=(r+1)/2;
61
  }
62
  return ans;
63
}
64

65
void solve(){
66
  cin>>n>>s;
67
  cout<<manacher(s)<<"\n";
68
}