この問題はランレングス符号化を用いて解くことができます。

同じ文字列が連続する箇所をまとめ、以下のように、「文字と整数の組の列」に変換することをランレングス符号化といいます。

aabbbca  -> (a,2)(b,3)(c,1)(a,1)
vwxyz    -> (v,1)(w,1)(x,1)(y,1)(z,1)

元の文字列から取り出したサンドイッチ区間は、元の文字列をランレングス符号化して得られる列の連続する3つの要素の一部分に対応します。

ccaaabbaaaaxxx  -> (c,2)(a,3)(b,2)(a,4)(x,3)
    abbaa       ->      (a,1)(b,2)(a,2)

\(S\) をランレングス符号化した連続 \(3\) 要素 \((c_1,n_1),(c_2,n_2),(c_3,n_3)\) に対応するサンドイッチ区間の個数を考えます。\(c_1\neq c_3\) のとき \(0\) です。\(c_1=c_3\) のとき、左右の要素をどれだけ残すかを考えることで、 \(n_1 \times n_3\) 個あることがわかります。

よってこれらの合計を求めれば良く、ランレングス符号化は \(O(N)\) で行えるため、この問題は \(O(N)\) で解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;

  vector<pair<char,int>>rle;
  char crr = s[0];
  int cnt = 0;
  for(char c: s){
    if(crr != c){
      rle.push_back({crr, cnt});
      cnt = 0;
    }
    crr = c;
    cnt++;
  }
  rle.push_back({crr, cnt});

  long long ans = 0;
  int m = rle.size();
  for(int i=0; i<m-2; i++){
    if(rle[i].first == rle[i+2].first){
      ans += (long long) rle[i].second * rle[i+2].second;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N = int(input())
S = input()

RLE = []
crr = S[0]
cnt = 0
for c in S:
  if crr != c:
    RLE.append((crr, cnt))
    cnt = 0
  crr = c
  cnt += 1
RLE.append((crr, cnt))

ans = 0
M = len(RLE)
for i in range(M-2):
  if RLE[i][0] == RLE[i+2][0]:
    ans += RLE[i][1] * RLE[i+2][1]

print(ans)