取り除く部分文字列の長さが異なれば最終的に得られる文字列も異なることに注意します．

\(S\) から \(S_L S_{L+1} \dots S_{R}\) を取り除いた文字列 \(S_1 S_2 \dots S_{L-1} S_{R+1} \dots S_N\) を \(S[L, R]\) と書くことにします．\(1 \leq L \leq R < N\) と \(0 < k \leq N - R\) に対し， \(S[L, R]=S[L+k, R+k]\) となる条件は \(S_L = S_{R+1}, S_{L+1} = S_{R+2},\dots, S_{L+k-1} = S_{R+k}\) が成り立つことです．このとき \(S[L, R], S[L+1,R+1], \dots, S[L+k, R+k]\) は全て等しいことが分かります．

よって，区間の選び方の個数 \(N(N+1)/2\) から，\(S[L,R]=S[L+1,R+1]\) となる \((L, R)\) の個数を引けばよいです． \(S[L,R]=S[L+1,R+1] \iff S_L = S_{R+1}\) であるので，この個数は文字 \(c\) の出現回数を \(f_c\) として \(\sum_c f_c(f_c-1)/2\) となります．

以上より，答えは \(N(N+1)/2 - \sum_c f_c(f_c-1)/2\) となります．