{"problem":{"name":"[语言月赛 202404] 非众数","description":{"content":"给定一个长度为 $n$ 的字符串 $s$，保证 $s$ 仅包含小写字母，求 $s$  的非空子串中非众数串的个数。 > **定义：非空子串** > > 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符（$1 \\leq i \\leq n$）。任取两个整数 $i, j$（$1 \\leq i \\leq j \\leq n$），将 $s_i, s_{i + 1}, \\cdots, s_{j}$ 截取出","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3967"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的字符串 $s$，保证 $s$ 仅包含小写字母，求 $s$  的非空子串中非众数串的个数。\n\n> **定义：非空子串**\n>\n> 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符（$1 \\leq i \\leq n$）。任取两个整数 $i, j$（$1 \\leq i \\leq j \\leq n$），将 $s_i, s_{i + 1}, \\cdots, s_{j}$ 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 $s$ 的非空子串。  \n例如，当 $s = \\texttt{abcde}$ 时，$\\texttt{ab}, \\texttt{bcde}, \\texttt{c}, \\texttt{abcde}$ 都是 $s$ 的非空子串，而 $\\texttt{acd}, \\texttt{f}, \\texttt{ngioasd}, \\texttt{\" \"}$ 都不是 $s$ 的非空子串。\n\n> **定义：非众数串**\n>\n> 若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\\lfloor \\frac{|a|}{2} \\rfloor$，则称字符串 $a$ 为一个**非众数**串。其中 $\\lfloor x \\rfloor$ 代表 $\\leq x$ 的最大整数，$|a|$ 代表 $a$ 的长度。\n\n## Input\n\n一行一个字符串，表示 $s$。\n\n## Output\n\n一行一个整数，表示答案。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n其中 $\\texttt{ab,aabb}$ 是**非众数**非空子串。\n\n### 数据范围\n\n对于 $100\\%$ 的数据，$1 \\le n \\le 500$，字符串由小写字母组成。\n\n| 测试点编号 | $n$ | 特殊性质 |\n| :-: | :-: | :-: |\n| $1$ | $= 2$ | 无 |\n| $2, 3$ | $\\leq 10$ | 无 |\n| $4$ | $\\leq 500$ | 所有字符相同 |\n| $5$ | $= 26$ | 所有字符不同 |\n| $6, 7$ | $\\leq 500$ | 字符串内仅可能包含 $\\texttt{a,b}$ 两种字母 |\n| $8 \\sim 10$ | $\\leq 500$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3967","tags":["2024","O2优化","字符串（入门）","函数与递归","语言月赛"],"sample_group":[["aabb","2"],["fqmdfnc\n","21\n"]],"created_at":"2026-03-03 11:09:25"}}