\(S\) の空でない部分文字列 \(O(N^2)\) 通りを全て列挙していては間に合わないので、代わりに「\(1\) 種類の文字のみからなる文字列のうち、\(S\) の部分文字列であるものの数を数える」という方針を考えます。

\(c=\) a, b, \(\dots\) ,z 、\(l=1,2,\dots\) に対して、\(c\) が \(k\) 文字連なってできる文字列を \(\text{str}(c,k)\) とします。\(S\) の中で文字 \(c\) が連続する回数の最大値を \(M(c)\) とおくと、\(\text{str}(c,k)\) が \(S\) の部分文字列であるための必要十分条件は \(k \leq M(c)\) ですから、求める答えは \(M(\)a\()+M(\)b\()+\dots+M(\)z\()\) と表されます。

あとは、\(M(c)\) の値を高速に求められれば良いです。これは、以下のようなアルゴリズムによって求められます。

1. 各 \(c\) について、\(M(c)=0\) と初期化する。\(l=r=1\) とする。
2. \(S\) の \(r\) 文字目と \(r+1\) 文字目が同じ文字である限り、\(r\) に \(1\) を足し続ける。なお、このとき \(S\) の \(l\) 文字目から \(r\) 文字目までは全て同じ文字である。
3. \(S\) の \(l\) 文字目を \(c\) としたとき、\(M(c) \leftarrow \max(M(c), r-l+1)\) と更新する。
4. \(l,r\) を \(r+1\) で更新する。\(l > N\) となったらアルゴリズムを終了する。そうでなければ 2. に戻る。

このアルゴリズムは \(O(N)\) で動作し、十分高速です。

なお、このアルゴリズムはランレングス圧縮と呼ばれる有名なアルゴリズムとほぼ同等ですので、知らなかった方はぜひ調べてみてください。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> mx(26);
    int l = 0;
    while (l < n) {
        int r = l + 1;
        while (r < n and s[l] == s[r]) ++r;
        int c = s[l] - 'a';
        mx[c] = max(mx[c], r - l);
        l = r;
    }
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans += mx[i];
    }
    cout << ans << endl;
}