题解：P1787 [入门赛 #22] 非众数 Hard Version

· · 题解

题意

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

思路

解决这个问题有许多方法，如树状数组或前缀和，今天将滑动窗口或双指针的方法，结合哈希表来记录每个字符在当前窗口中的出现次数，从而判断当前窗口内的串是不是非众数。

具体的思路实现

首先遍历字符串 s 的每一个可能的子串。建立一个计数器 ans，ans 的初值为零，对于每一个子串，使用一个数组来记录子串中每个字符的出现次数。检查当前子串中出现次数最多的字符的出现次数是否不超过子串长度的一半（注意，这里需要向下取整），如果是，则该子串满足条件，ans 就加一，最后输出 ans。