Unique Character Substring Sum

Given a string \(S\) of length \(n\), we define \(f(S)\) as the number of characters in \(S\) that appear exactly once. For example, \(f(\text{'aba'}) = 1\), \(f(\text{'abc'}) = 3\), and \(f(\text{'aaaa'}) = 0\). The task is to compute the sum of \(f(S[i\ldots j])\) over all non-empty substrings \(S[i\ldots j]\) of \(S\) where \(0 \le i \le j < n\).

Hint: One efficient approach is to notice that each character in \(S\) contributes to several substrings where it is the unique occurrence. By finding for every occurrence the distance to its previous and next occurrence, one can compute its total contribution.

inputFormat

The input consists of a single line containing the string \(S\).

outputFormat

Output a single integer representing the sum of \(f(S[i\ldots j])\) over all non-empty substrings of \(S\).

sample

aba

8