Background

This problem is the Hard Version of "Non-Majority," with $1 \le n \le 10^5$. Thanks to @yummy for the contribution.

Problem Description

Given a string $s$ of length $n$, where $s$ consists only of lowercase letters, find the count of non-empty substrings of $s$ that are non-majority strings.

Definition: Non-empty Substring

Let $s_i$ represent the $i$-th character of $s$ (where $1 \leq i \leq n$). For any two integers $i$ and $j$ (where $1 \leq i \leq j \leq n$), the substring formed by $s_i, s_{i + 1}, \cdots, s_{j}$ in their original order is a non-empty substring of $s$.
For example, when $s = \texttt{abcde}$, $\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ are all non-empty substrings of $s$, while $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ are not.

Definition: Non-Majority String

If the most frequent character in string $a$ appears no more than $\lfloor \frac{|a|}{2} \rfloor$ times, then string $a$ is a non-majority string. Here, $\lfloor x \rfloor$ denotes the largest integer not greater than $x$, and $|a|$ denotes the length of $a$.

Input Format

A single line containing the string $s$.

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

aabb

Sample Output #1

2

Sample Input #2

fqmdfnc

Sample Output #2

21

Notes

Sample 1 Explanation

Among the substrings, $\texttt{ab}$ and $\texttt{aabb}$ are non-majority non-empty substrings.

Data Range

For $100\%$ of the data, $1 \le n \le 10^5$, and the string consists of lowercase letters.

见题面 Input 部分

见题面 Output 部分