当区间中包含所有三个字符时，设出现次数分别为 $c_1, c_2, c_3$，那么极差可以用 $\frac{1}{2} (|c_1 - c_2| + |c_2 - c_3| + |c_3 - c_1|)$ 来计算。包含两种不同字符时，极差可以仅考虑这两种字符的贡献。当仅包含一种字符时，对答案没有贡献。

考虑枚举不同的字符对，并计算包含三个字符的区间的贡献，以及正好包含这两个字符的区间的贡献。从左往右扫描整个字符串，设当前右端点为 $r$，维护三个字符的最后出现位置，即可快速计算出两个分界点 $p_1, p_2$，表示左端点在 $[1, p_1]$ 中时包含三个字符，在 $[p_1 + 1, p_2]$ 中时正好包含当前考虑的两个字符。将两个字符一个权值记为 $1$，一个记为 $-1$，不被考虑的那个字符记为 $0$，那么区间的贡献即为区间权值和的绝对值。在每个左端点处插入前缀和，在右端点查询前缀和的位置的所有贡献和即可。由于 $p_1, p_2$ 是不断向右移动的，所以插入次数是 $\mathcal{O}(N)$。而查询时之前每个插入都有差值绝对值的系数，而查询的位置每次只变化 $\mathcal{O}(1)$，所以只需要维护三个变量：当前贡献和，比当前查询位置小的插入数量，以及比当前查询位置大的插入数量。移动查询位置时，贡献变化量可以快速计算。

于是总时间复杂度是 $\mathcal{O}(N)$ 的。