解题思路

关键观察

• 只关心奇偶性（每种字母出现次数 mod 2）。
• 令 mask[i] 表示前缀 s[1..i] 的 26 位奇偶掩码（第 $k$ 位为该字母出现次数的奇偶）。
• 子串 s[l..i] 的掩码为 mask[l-1] ^ mask[i]。
• 若该子串“无害”，则 popcount(mask[l-1] ^ mask[i]) ∈ {0,1}（全 0 或恰好一个 1）。

状态设计

题目内容

小红是一个魔法项链回收商，他的工作是将这些魔法项链进行无害化处理，魔法项链由若干颗魔法石组成，可以视作一个字符串，不同种类的魔法石可以用小写字母 $a$ ~ $z$ 来进行表示。小红可以将魔法项链切割为若于段(也可以不切割)，每一段中相同种类的魔法石可以进行能量抵消，如果最终宝石全部抵消或者只剩一颗，那么就算完成了无害化处理。

例如：

项链段 $zz$ 可以完成无害化。

项链段 $aba$ 可以完成无害化，$aa$ 可以抵消，最后只一颗 $b$ ；

项链段 $cccg$ 不可以完成，因为 $cc$ 抵消后还剩下 $cg$ ，不止一颗。

今天小红又回收到了一条魔法项链，他想知道最少需要将魔法项链切割成多少子段，可以使所有子段都可以完成无害化处理。

输入描述

一个字符串，只包含小写字母，用来表示小红回收的魔法项链，长度不超过 $100000$

输出描述

一个整数，表示最小需要切割为多少段，可以使所有项链子段都能完成无害化处理。

样例1

输入

xyz

输出

3

样例2

输入

abcdabcd

输出

1

说明

无需切割，最初的项链串本身就可以完成无害化处理，此时记为 $1$ 段。

样例3

输入

rrzbbaau

输出

2

说明

可以切割为 $rrz,bbaau$ 两个子串。