Background

This problem is the Hard Version of “Non-majority String”. Here $1 \le n \le 10^5$. Thanks to

Problem Description

Given a string $s$ of length $n$, where $s$ is guaranteed to contain only lowercase letters, find the number of non-empty substrings of $s$ that are non-majority strings.

Definition: non-empty substring

Let $s_i$ denote the $i$-th character of $s$ ($1 \leq i \leq n$). Choose any two integers $i, j$ ($1 \leq i \leq j \leq n$), and take $s_i, s_{i + 1}, \cdots, s_{j}$ in the original order to form a new string. This new string is called a non-empty substring of $s$.
For example, when $s = \texttt{abcde}$, $\texttt{ab}$, $\texttt{bcde}$, $\texttt{c}$, and $\texttt{abcde}$ are all non-empty substrings of $s$, while $\texttt{acd}$, $\texttt{f}$, $\texttt{ngioasd}$, and $\texttt{" "}$ are not.

Definition: non-majority string

If, in a string $a$, the maximum frequency among all characters is not greater than $\lfloor \frac{|a|}{2} \rfloor$, then the string $a$ is called a non-majority string. Here $\lfloor x \rfloor$ denotes the greatest integer $\leq x$, and $|a|$ denotes the length of $a$.

Input Format

One line containing a string $s$.

Output Format

One line containing an integer, the answer.

aabb

2

fqmdfnc

21

Hint

Sample 1 Explanation

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

Constraints

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

Translated by ChatGPT 5