/ 
Time Limit: 3 sec / Memory Limit: 512 MB
配点 : 700 点
問題文
英小文字のみからなる文字列 s があります。 すぬけ君は、s をいくつかの空でない部分文字列へ分割しようとしています。 分割後の部分文字列を、左から順に s_1, s_2, ..., s_N とします (このとき、s = s_1 + s_2 + ... + s_N です)。 すぬけ君は、次の条件が成り立つように s を分割しようとしています。
- 各 i (1 \leq i \leq N) について、s_i の文字を並べ替えて回文が得られる。
条件が成り立つように s を分割するとき、N の最小値を求めてください。
制約
- 1 \leq |s| \leq 2 \times 10^5
- s は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
s
出力
条件が成り立つように s を分割するとき、N の最小値を求めよ。
入力例 1
aabxyyzz
出力例 1
2
aabxyyzz = aab + xyyzz と分割すればよいです。
このとき、aab の文字を並べ替えて回文 aba が得られ、xyyzz の文字を並べ替えて回文 zyxyz が得られます。
入力例 2
byebye
出力例 2
1
byebye の文字を並べ替えて回文 byeeyb が得られます。
入力例 3
abcdefghijklmnopqrstuvwxyz
出力例 3
26
入力例 4
abcabcxabcx
出力例 4
3
abcabcxabcx = a + b + cabcxabcx と分割すればよいです。
Score : 700 points
Problem Statement
We have a string s consisting of lowercase English letters. Snuke is partitioning s into some number of non-empty substrings. Let the subtrings obtained be s_1, s_2, ..., s_N from left to right. (Here, s = s_1 + s_2 + ... + s_N holds.) Snuke wants to satisfy the following condition:
- For each i (1 \leq i \leq N), it is possible to permute the characters in s_i and obtain a palindrome.
Find the minimum possible value of N when the partition satisfies the condition.
Constraints
- 1 \leq |s| \leq 2 \times 10^5
- s consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
Output
Print the minimum possible value of N when the partition satisfies the condition.
Sample Input 1
aabxyyzz
Sample Output 1
2
The solution is to partition s as aabxyyzz = aab + xyyzz.
Here, aab can be permuted to form a palindrome aba, and xyyzz can be permuted to form a palindrome zyxyz.
Sample Input 2
byebye
Sample Output 2
1
byebye can be permuted to form a palindrome byeeyb.
Sample Input 3
abcdefghijklmnopqrstuvwxyz
Sample Output 3
26
Sample Input 4
abcabcxabcx
Sample Output 4
3
The solution is to partition s as abcabcxabcx = a + b + cabcxabcx.