思路分析

关键观察

1. 回文的结构 一个回文的字符频率结构：

   • 如果长度是偶数 → 每个字符出现次数均为偶数；
   • 如果长度是奇数 → 恰好有一个字符出现次数为奇数，其他为偶数。

题目内容

包包有一个长度为 $n$ 的，仅由小写英文字母构成的字符串 $s$ 。你需要将 $s$ 中的字符任意重排后，划分成若干个连续子串，使得每个字符被恰好一个字串包含，且每个子串都为回文串。请问最少需要划分成多少个连续子串？

【子串】子串为从原字符串中，连续的选择一段字符(可以全选)得到的新字符串。

【回文串】一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述

输入一行一个仅由小写英文字母构成的字符串 $s(1≦|s|≦ 10^5)$ ，其中 $|s|$ 表示 $s$ 的长度。

输出描述

输出一个整数，表示最少需要划分成多少个连续子串。

样例1

输入

baozii

输出

4

说明

我们可以先将 $baozii$ 重排后变成 $baoizi$ ，然后划分成 $b,a,o,izi$ $4$ 个连续子串，且都为回文串。可以证明，不在一种重排和划分方式使得划分出的子串数量小于 $4$ 。

样例2

输入

zrnstnsr

输出

2