语言月赛 202404 非众数

题意理解

给定一个字符串 $s$，你需要找出它所有非空子串中，是 非众数串 的子串总数。

非众数串定义：

• 对任意一个子串 $a$，如果其中出现次数最多的字符（众数）不超过 $\lfloor \frac{|a|}{2} \rfloor$，则该子串是非众数串。
• 举例：
• 子串 ab 长度为 $2$，最多允许一个字符出现一次，实际 a 和 b 都只出现一次，合法；
• 子串 aaa 长度为 $3$，最多允许一个字符出现 $1$ 次，但 a 出现了 $3$ 次，因此不是非众数串。

---

解题思路

暴力方法分析

由于字符串长度 $n \leq 500$，最多存在 $\frac{n(n+1)}{2}$ 个非空子串，约 $125000$ 级别，配合每次 $O(26)$ 的统计复杂度，可以接受。

实现流程：

• 定义 int n = s.size()。
• 枚举所有子串 $s[i..j]$（$0 \le i \le j \le n-1$）。双重循环嵌套枚举 $i,j$。
• 对每个子串，统计每个字符的出现次数（只需要统计 $26$ 个小写字母）。
  • 在循环嵌套内，定义一个大小为 $26$ 的数组 cnt，统计每个小写字母出现几次。
• 找到该子串中最多的字符次数，记为 $mx$。
• 判断是否满足 $mx \leq \lfloor \frac{\text{子串长度}}{2} \rfloor$。其中子串长度为 $j-i+1$。
  • 若满足，计数器加一；
• 最后输出总数。

---

时间复杂度分析

• 总共 $O(n^2)$ 个子串；
• 每个子串判断是否是非众数串，耗时 $O(26)$；
• 总复杂度：$O(n^2 \cdot 26)$，对 $n = 500$ 可接受。

---

总结

• 本题的关键是理解「非众数」定义，即众数字符不能超过子串长度的一半；
• 暴力统计每个子串字符频率即可；
• 适合巩固枚举 + 频率统计等基础方法；
• 可进一步优化（如滑动窗口维护频率表），但对本题数据范围不需要。