分数: 700 点
问题陈述
我们有一个字符串 s 由小写英文字母组成。 Snuke 正在分区 s 到一定数量的非空子字符串中。 获取子串 s_1, s_2, ..., s_N 从左到右。 s = s_1 + s_2 + ... + s_N 成立。) Snuke想要满足以下条件:
- 对于每个 i (1 \leq i \leq N),可以排列其中的字符 s_i 并获得回文。
找到最小可能值 N 当分区满足条件时。
约束
- 1 \leq |s| \leq 2 \times 10^5
- s 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
s
输出
打印最小可能值 N 当分区满足条件时。
样本输入 1
aabxyyzz
示例输出 1
2
解决办法是分区 s as aabxyyzz = aab + xyyzz。
在这里, aab 可以排列形成回文 aba,和 xyyzz 可以排列形成回文 zyxyz.
示例输入 2
byebye
示例输出 2
1
byebye 可以排列形成回文 byeeyb.
示例输入 3
abcdefghijklmnopqrstuvwxyz
示例输出 3
26
示例输入 4
abcabcxabcx
示例输出 4
3
解决办法是分区 s as abcabcxabcx = a + b + cabcxabcx.