We cannot enumerate all the \(O(N^2)\) non-empty strings of \(S\) within the time limit. Instead, we try to count the number of strings consisting of only one character, that are substrings of \(S\).

For \(c=\) a, b, \(\dots\) ,z and \(l=1,2,\dots\), let \(\text{str}(c,k)\) be \(k\)-time repetition of \(c\). If we let \(M(c)\) be the maximum consecutive occurrences of the character \(c\) in \(S\), then \(\text{str}(c,k)\) is a substring of \(S\) if and only if \(k \leq M(c)\); so the sought answer is represented as \(M(\)a\()+M(\)b\()+\dots+M(\)z\()\).

All that left is to find \(M(c)\) fast enough. They can be obtained by the following algorithm.

1. For each \(c\), initialize with \(M(c)=0\). Let \(l=r=1\).
2. While the \(r\)-th and \((r+1)\)-th characters of \(S\) are the same, add \(1\) to \(r\). Here, the \(l\)-th through \(r\)-th characters of \(S\) are all the same.
3. Let \(c\) be the \(l\)-th character of \(S\). Update \(M(c) \leftarrow \max(M(c), r-l+1)\).
4. Set \(l\) and \(r\) to \((r+1)\). If \(l > N\), terminate the algorithm. Otherwise, go back to 2..

This algorithm operates in \(O(N)\) time, which is fast enough.

In fact, this algorithm is almost identical to what is called “run-length encoding,” so if you did not know the concept, we recommend you to learn it.

Sample code (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;
}