← 返回题目列表

AtCoder · code_festival_2017_qualc_d

D. 又一个回文分区

中文机器翻译题面 查看原题

分数: 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.