概略

• \(S\) の \(i\) 文字目と \(j\) 文字目が違う文字なら、その \(2\) 文字を入れ替えてできる文字列は \(S\) と異なる
• そのようにして作られる文字列は \((i,j)\) の選び方が違えば異なるものになる
• なのでだいたい「\(S\) の \(i\) 文字目と \(j\) 文字目が違う文字であるような組 \((i,j)\) は何個あるか？」が求められればよい
• 頑張って求める

詳細

例えば \(S\) が aaabbc のとき、 \(3\) 文字目は a、\(6\) 文字目は c であり、この \(2\) 文字を入れ替えてできる文字列は aacbba となります。こうして作られた文字列は \(S\) とは \(3\) 文字目と \(6\) 文字目が違います。 逆に aacbba のように、\(S\) とは \(3\) 文字目と \(6\) 文字目が違う文字列を作るには(もし作れるなら) \(S\) の \(3\) 文字目と \(6\) 文字目を入れ替えて作るしかありません。

よって、\(S\) の \(i\) 文字目と \(j\) 文字目が違う文字であれば、その \(2\) 文字を入れ替えて作られる文字列は、他の操作により作ることができません。つまり \(S\) が aaabbc のときは以下の \(2\) 文字を入れ替えることで作られる文字列は相異なることがわかります。

• \(1\) 文字目の a と \(4\) 文字目の b
• \(1\) 文字目の a と \(5\) 文字目の b
• \(1\) 文字目の a と \(6\) 文字目の c
• \(2\) 文字目の a と \(4\) 文字目の b
• \(2\) 文字目の a と \(5\) 文字目の b
• \(2\) 文字目の a と \(6\) 文字目の c
• \(3\) 文字目の a と \(4\) 文字目の b
• \(3\) 文字目の a と \(5\) 文字目の b
• \(3\) 文字目の a と \(6\) 文字目の c
• \(4\) 文字目の b と \(6\) 文字目の c
• \(5\) 文字目の b と \(6\) 文字目の c

\(S\) の \(i\) 文字目と \(j\) 文字目が同じ文字であれば、その \(2\) 文字を入れ替えて作られる文字列は \(S\) と同じになります。逆に \(S\) を作るには、等しい文字を入れ替えるしかありません。よって \(S\) に \(2\) 度以上登場する文字が存在する場合には、\(S\) 自身が作れる分として答えに \(1\) を加える必要があります。

考察パート2

「\(S\) の \(i\) 文字目と \(j\) 文字目が違う文字であるような組 \(\{i,j\}\) は何個あるか？」が求められればよいことがわかりました。

これは \(\{i,j\}\) を全探索することで \(\Theta(N^2)\) で求めることができますが、TLE(実行時間制限超過)になります。より高速な方法を考える必要があります。

いくつか方法はありますが思いつきやすいのは、文字ごとではなく文字種ごとに考える方法でしょう。\(j\) を全探索し、\(j\) を決めるごとに \(i\) をいくつ選べるかを考えます。\(i\) として選べないのは、\(j\) と同じ文字の箇所なので、今までにどの文字が何回登場しているかを数えておけば求めることができます。

from collections import defaultdict
S=input()
N=len(S)
ans=0
count=defaultdict(int)
for j in range(N):
  ans+=j-count[S[j]]  # i として選べるのは、j までの文字のうち S[j] と同じでないもの
  count[S[j]]+=1
if max(count.values())>1:
  ans+=1
print(ans)

別の方針も考えられます。数えたい \(\{i,j\}\) に丸印をつけた表を用意し、それを斜めに折り返します。さらに表の行・列を並び替えます。

これにより求める値は
\((N^2 - (aの個数の2乗)-(bの個数の2乗)-\ldots)/2\)
であることがわかります。

from collections import Counter
S=input()
N=len(S)
count=Counter(S)
ans=(N*N-sum(x*x for x in count.values()))//2
if max(count.values())>1:
  ans+=1
print(ans)