https://inamori.hateblo.jp/entry/2024/10/13/151026

https://atcoder.jp/contests/abc375/tasks/abc375_d

文字ごとにポジションを配列にして、それをxと書くと、その配列のサイズをNとして、

$\displaystyle \sum_{i \lt j}{(x_j-x_i-1)} = \sum_{j=1}^{N-1}{\sum_{i=0}^{j-1}{(j(x_j-1) - \sum_{i=0}^{j-1}{x_i})}}$

$\displaystyle s_j \equiv \sum_{i=0}^{j-1}{x_i}$

とすると、

$\sum_{j=1}^{N-1}{(j(x_j-1)-s_j)}$

となって、 $O(N)$ で計算できます。

// ABA
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn classify(S: &String) -> HashMap<char, Vec<usize>> {
    let mut cl: HashMap<char, Vec<usize>> = HashMap::new();
    for (p, c) in S.chars().enumerate() {
        let e = cl.entry(c).or_insert(vec![]);
        (*e).push(p)
    }
    return cl
}

fn F_each(v: Vec<usize>) -> usize {
    let N = v.len();
    let mut s: usize = 0;
    let mut a: usize = 0;
    for j in 1..N {
        a += v[j-1];
        s += j * (v[j] - 1) - a
    }
    s
}

fn F(S: String) -> usize {
    let cl = classify(&S);
    cl.into_iter().map(|(_, v)| F_each(v)).sum::<usize>()
}

fn main() {
    let S: String = read();
    println!("{}", F(S))
}