Dễ dàng nhận thấy là các xâu khác xâu ban đầu nhận được bằng cách đổi chỗ ~2~ kí tự khác nhau. Gọi ~cnt_c~ là số lượng kí tự ~c~ có trong xâu và ~n~ là độ dài xâu trong xâu thì số xâu khác xâu ban đầu sẽ bằng: ~\frac{1}{2}\sum_{c=a}^{z} cnt_c\times(n-cnt_c)~

Tuy nhiên nếu trong xâu có kí tự ~c~ nào đó mà ~cnt_c>1~ thì khi đổi chỗ ~2~ kí tự giống nhau đó thì ta còn nhận được thêm xâu ban đầu. Nên nếu có ~cnt_c>1~ thì đáp án sẽ phải cộng thêm ~1~.

Độ phức tạp: ~O(n \times 26)~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int f[39];

int main()
{
    fastIO

    string s;
    cin>>s;

    int n = s.size();
    s = ' ' + s;

    ll cnt = 1;
    for (int i = 1;i <= n; ++i) f[s[i]-'a']++;

    bool flag = true;

    for (int i = 0; i < 26; ++i)
        if (f[i] > 1)
            flag = false;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 26; ++j)
                if (j != s[i] - 'a') cnt += f[j];
        --f[s[i]-'a'];
    }

    return cout<<cnt-flag, 0;
}