P8715 [Lanqiao Cup 2020 NOI Qualifier AB2] Substring Value

For a string $S$, we define its value $f(S)$ as the number of characters that appear exactly once in $S$. For example, $f\left({ }^{\prime \prime} \mathrm{aba}{ }^{\prime \prime}\right)=1$, $f\left({ }^{\prime \prime} \mathrm{abc}{ }^{\prime \prime}\right)=3$, and $f\left({ }^{\prime \prime} \mathrm{aaa} \mathrm{a}^{\prime \prime}\right)=0$. Now given a string $S[0..n-1]$ (with length $n$), please compute the sum of $f(S[i..j])$ over all non-empty substrings $S[i..j]$ $(0 \leq i \leq j < n)$.

Input one line containing a string $S$ consisting of lowercase letters.

Output an integer representing the answer.

For $20\%$ of the testdata, $1 \leq n \leq 10$. For $40\%$ of the testdata, $1 \leq n \leq 100$. For $50\%$ of the testdata, $1 \leq n \leq 1000$. For $60\%$ of the testdata, $1 \leq n \leq 10000$. For all testdata, $1 \leq n \leq 100000$. Lanqiao Cup 2020, second round provincial contest, Group A Problem H (Group B Problem H). Translated by ChatGPT 5