ABAB

2 secs 1024 MB

解説

$S$ の $i$ 番目の文字を $S_i$ とします。

求める部分列を $S_iS_jS_kS_l,(i<j<k<l)$ とします。

$S_i = S_k$ が成り立つ時、 $S_j = S_l$ の組み合わせがどれだけ作れるかを数えます。

$i < j < k$ での各文字の出現個数と、 $k < l \leqq n$ での文字の出現個数をカウントしておきます。

そして、 $S_i = S_k$ が成り立つ時に限り、事前に数えておいた $S_j = S_l$ のペアの個数を求めればよいです。