不难发现答案 \(\le 15\)，极限的情况大概就是 \(aabbcc\cdots gghh\)，此时跳一步和走一步等效。
这启示我们固定点 \(i\)，统计 \(d(i,j)=D,j<i\) 的 \(j\) 的个数，拆成 \(i-j\le 15\) 的贡献和 \(i-j>15\) 的贡献。
为了方便，以下称从 \(i\) 到 \(i+1\) 或 \(i-1\) 为「走」，在相同颜色的点之间移动为「跳」。对于既可能拥有「走」操作有可能拥有「跳」操作的移动过程，称之为「跑」。
\(i-j\le 15\) 的贡献
一种情况是 \(j\) 直接走到 \(i\)，步数为 \(i-j\)。
另一种情况是 \(j\) 先跑到一个点 \(k\)，然后 \(k\) 再跳到和它相同颜色的点 \(l\)，再由 \(l\) 跑到 \(i\)，即 \(j\to k\to l\to i\)。
为了方便，预处理出 \(f_{i,c}\) 表示 \(i\) 跑到任意一个颜色为 \(c\) 的点的最短距离，\(g_{c_1,c_2}\) 为任意两个颜色分别为 \(c_1,c_2\) 的点之间，\(c_1\) 跑到 \(c_2\) 的最短距离。由于边权相同，可以 bfs 求出。
于是 \(j\to k\to l\to i\) 的最小步数为 \(\min\limits_{c}\{f_{j,c}+f_{i,c}+1\}\)。
两种情况取 \(\min\) 即可算出 \(j\to i\) 的最短距离。枚举 \(i\)，枚举前 \(15\) 个数即可，复杂度 \(O(kn)\)，\(k=15\)。
\(i-j>15\) 的贡献
只有可能是 \(\min\limits_c\{f_{j,c}+f_{i,c}+1\}\)。但是无法枚举所有的 \(j\) 取 \(\min\)。
发现 \(f_{i,c}\) 要么是 \(g_{a_i,c}\) 要么是 \(g_{a_i,c}+1\)，而颜色数很少，考虑状态压缩。把每个点压成二元组 \((a_i,\text{st})\)，\(\text{st}\) 为 \(8\) 位二进制数，第 \(c\) 位 \(\text{st}(c)\) 表示 \(f_{i,c}\) 为 \(g_{a_i,c}\) 或者 \(g_{a_i,c}+1\)。
对于相同的二元组 \((x,\text{st})\)，映射到不同的点。但是这些点到 \(i\) 的距离都是相同的，为 \(\min\limits_c\{f_{i,c}+1+g_{x,c}+\text{st}(c)\}\)，可以一起统计进答案里面。复杂度降为 \(O(p^22^pn)\)，\(p=8\)，稍微剪枝就过了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
// #if ONLINE_JUDGE
// #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
// #else
#define gh() getchar()
// #endif
#define rd read
#define wr write
#define pc putchar
#define pi pair<int, ll>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(ll x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int N = 1e5 + 100;
const int T = (1 << 8) + 100;
const int inf = 0x3f3f3f3f;
int n, a[N], vs[N], vc[10], f[N][10], g[10][10], ct[10][T];
char s[N];
vector<int> c[N];
pi ans;
void chk(pi &x, pi y) {
if (y.fi > x.fi) x = y;
else if (y.fi == x.fi) x.se += y.se;
}
void init() {
memset(f, inf, sizeof(f));
memset(g, inf, sizeof(g));
for (int i = 0; i <= 7; i++) {
queue<int> q;
for (int j = 0; j <= 7; j++) vc[j] = 0;
for (int j = 1; j <= n; j++) vs[j] = 0;
for (int j : c[i])
q.push(j), f[j][i] = 0, vs[j] = 1;
g[i][i] = 0, vc[i] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u > 1) {
int v = u - 1;
if (!vs[v])
f[v][i] = f[u][i] + 1, vs[v] = 1, q.push(v);
}
if (u < n) {
int v = u + 1;
if (!vs[v])
f[v][i] = f[u][i] + 1, vs[v] = 1, q.push(v);
}
if (vc[a[u]]) continue;
vc[a[u]] = 1, g[a[u]][i] = f[u][i];
for (int v : c[a[u]])
if (!vs[v])
f[v][i] = f[u][i] + 1, vs[v] = 1, q.push(v);
}
}
}
int st(int x) {
int res = 0;
for (int i = 0; i <= 7; i++)
if (f[x][i] == g[a[x]][i] + 1) res |= (1 << i);
return res;
}
int main() {
n = rd(), scanf("%s", s + 1);
for (int i = 1; i <= n; i++)
a[i] = s[i] - 'a', c[a[i]].pb(i);
init();
for (int i = 2; i <= n; i++) {
for (int j = max(1, i - 15); j <= i - 1; j++) {
int tp = i - j;
for (int k = 0; k <= 7; k++) tp = min(tp, f[i][k] + f[j][k] + 1);
chk(ans, mp(tp, 1));
}
}
for (int i = 17; i <= n; i++) {
ct[a[i - 16]][st(i - 16)]++;
for (int j = 0; j <= 7; j++) {
for (int k = 0; k <= (1 << 8) - 1; k++) {
if (!ct[j][k]) continue;
int w = n + 1;
for (int l = 0; l <= 7; l++)
w = min(w, f[i][l] + g[j][l] + ((k >> l) & 1) + 1);
chk(ans, mp(w, ct[j][k]));
}
}
}
wr(ans.fi), pc(' '), wr(ans.se);
return 0;
}