P1787 [Beginner Contest #22] Non-majority String Hard Version

This problem is the Hard Version of “Non-majority String”. Here $1 \le n \le 10^5$. Thanks to @[yummy](https://www.luogu.com.cn/user/101694) for the contribution.

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$.

One line containing a string $s$.

One line containing an integer, the answer.

### 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