#1804. [语言月赛 202404] 非众数

[语言月赛 202404] 非众数

题目描述

给定一个长度为 nn 的字符串 ss,保证 ss 仅包含小写字母,求 ss 的非空子串中非众数串的个数。

定义:非空子串

用 sis_i 表示 ss 中的第 ii 个字符(1≤i≤n1 \leq i \leq n)。任取两个整数 i,ji, j(1≤i≤j≤n1 \leq i \leq j \leq n),将 si,si+1,⋯ ,sjs_i, s_{i + 1}, \cdots, s_{j} 截取出来按原序排列作为一个新的字符串,则这个字符串叫做 ss 的非空子串。
例如,当 s=abcdes = \texttt{abcde} 时,$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 ss 的非空子串,而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 ss 的非空子串。

定义:非众数串

若字符串 aa 中出现次数最多的字符出现的次数不超过 ⌊∣a∣2⌋\lfloor \frac{|a|}{2} \rfloor,则称字符串 aa 为一个非众数串。其中 ⌊x⌋\lfloor x \rfloor 代表 ≤x\leq x 的最大整数,∣a∣|a| 代表 aa 的长度。

输入格式

一行一个字符串,表示 ss。

输出格式

一行一个整数,表示答案。

样例

aabb
2
fqmdfnc
21

题目来源:洛谷 B3967