数えるべき \((l _ 1,r _ 1),(l _ 2,r _ 2)\ (l _ 1\le l _ 2)\) の組について、\(d\coloneqq l _ 2-l _ 1\) の値を固定して考えます。 \(d\) は \(1\) 以上 \(N-1\) 以下の整数になります。

\(f _ i\coloneqq\bigl(s _ i\ne s _ {i+d}\) なら \(1\) 、そうでなければ \(0\bigr)\) として \(f _ 1,f _ 2,\ldots,f _ {N-d}\) を定めます。 すると、\((l _ 1,r _ 1),(l _ 1+d,r _ 1+d)\) が条件を満たすことは、\(\displaystyle\sum _ {i=l _ 1} ^ {r _ 1}f _ i=1\) であることと同値です。

\(f _ i=1\) であるような \(i\) を求めておくことで、このような区間 \((l _ 1,r _ 1)\) を数え上げることができます。

時間計算量は \(O(N ^ 2)\) となります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <print>

int main() {
    using namespace std;
    int N;
    string S;
    cin >> N >> S;

    long ans = 0;
    for (int d = 1; d < N; ++d) { // ありえる d ごとに
        vector<int> diff_index; // f_i = 1 となる i を求める
        diff_index.emplace_back(); // 番兵を置いておく
        for (int i = 0; i + d < N; ++i)
            if (S[i] != S[i + d])
                diff_index.emplace_back(i + 1);
        diff_index.emplace_back(N - d + 1); // 番兵を置いておく

        int M = diff_index.size();
        for (int i = 0; i + 2 < M; ++i) {
            ans += (diff_index[i + 2] - diff_index[i + 1]) * (diff_index[i + 1] - diff_index[i]); // i 番目の 1 から隣の 1 まで左右に独立に伸ばせる
        }
    }
    cout << ans << endl;
    return 0;
}

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

ans = 0
for d in range(1, N): # ありえる d ごとに
    diff_index = [] # f_i = 1 となる i を求める
    for i in range(N - d):
        if S[i] != S[i + d]:
            diff_index.append(i + 1)
    diff_index = [0] + diff_index + [N - d + 1] # 番兵を置いておく

    for i in range(len(diff_index) - 2):
        ans += (diff_index[i + 2] - diff_index[i + 1]) * (diff_index[i + 1] - diff_index[i]) # i 番目の 1 から隣の 1 まで左右に独立に伸ばせる

print(ans)