問題概要

長さ $N$ の文字列 $S$ が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。

$1 \le i \lt j \le N$ を満たす $i, j$ を好きなように選んで、 $S$ の $i$ 文字目と $j$ 文字目を swap する

制約

$2 \le N \le 10^{6}$

考えたこと

$S_{i}$ と $S_{j}$ が同じ文字である場合には、これらを swap しても $S$ のまま変わらないということに注意しましょう。よって、操作によってできる文字列のうち、

$S$ のままであるもの
$S$ 以外になるもの

とに分けて考えるとよいだろう。

$S$ のままであるもの

これはすなわち操作した結果が $S$ となりうることがありうるかどうかを考えればよい。これは単純に

$S$ が同じ文字を含むとき： $S$ を作れる（1 通り）
$S$ の文字がすべて相異なるとき： $S$ を作れない（0 通り）

となる。

$S$ 以外になるもの

まず、 $i, j$ 文字目を入れ替えるとしたとき、 $S_{i}$ と $S_{j}$ とが異なる必要がある。

ここで気になるのは、ある $i, j$ に対する操作後の結果が、他の $i, j$ に対する操作後の結果と一致することがあるかどうかだ。もし一致するものがあるならば、それらは 1 つと数えなければならない。

しかし、その心配はない。 $S_{i}$ と $S_{j}$ が異なるということは、「操作後の文字列は、もとの文字と $i, j$ 文字目が異なる」ことを意味するのだ。 $i, j$ が変われば、操作後の文字列は当然変わるのだ。

よって、 $S_{i} \neq S_{j}$ であるような $(i, j)$ の個数を求めればよい。それを求めるためには、「すべての $(i, j)$ の選び方」から、「 $S_{i} = S_{j}$ となる $(i, j)$ の選び方」を引くのが良いだろう。

「 $S_{i} = S_{j}$ となる $(i, j)$ の選び方」を求めるためには、次の配列を求めよう。

cnt[c] ← 文字列 $S$ に含まれる文字 $c$ の個数

そうすれば、各文字 $c$ に対する cnt[c] * (cnt[c] - 1) / 2 を合算することで求められる。

以上の解法は、 $O(N)$ の計算量となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    long long N = S.size(), res = N * (N - 1) / 2;

    long long can_S = 0;
    vector<long long> cnt(26);
    for (int i = 0; i < N; i++) cnt[S[i] - 'a']++;
    for (int v = 0; v < 26; v++) {
        if (cnt[v] >= 2) can_S = 1;
        res -= cnt[v] * (cnt[v] -  1) / 2;
    }
    cout << res + can_S << endl;
}