D - Yet Another Palindrome Partitioning

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.