彩旗切割

题目描述

森林运动会前夕，乐柠兔收到了她预定的彩旗，可是商家把所有彩旗串在了一起， 其中用字符串 $s$ 表示连续彩旗的颜色（每个字母代表一种颜色）。为了让彩旗更美观，她需要把整串彩旗分成成一个或多个美观的彩旗段。

定义：一个字符串是美观的，当且仅当其中每种出现过的字符出现次数都相同。

例如：

• xxyzz 不是美观的（计数为 x:2,y:1,z:2，不相等）；
• zyzy、xxx、opq 是平衡串（分别是 z:2,y:2；x:3；o:1,p:1,q:1）。

请你计算：将 $s$ 分成为若干个连续子串后，使得每个子串都是美观的前提下，最少需要切成多少段。

输入格式

第一行：一个字符串 $s$，仅包含小写英文字母。

输出格式

输出一个整数，表示最少切成的平衡子串数量。

样例输入 1

abcddeef

样例输出 1

3

样例解释 1

一种可行切割为：abc | ddee | f。

• abc 中各字母均出现 1 次；
• ddee 中 d:2,e:2；
• f 中 f:1。 无法在保证每段美观的同时用少于 3 段覆盖全串。

样例输入 2

xyxyxyxmmnny

样例输出 2

2

样例解释 2

可切为：xyxy | xyxmmnny。

• xyxy 中 x:2,y:2；
• xyxmmnny 中 x:2,y:2,m:2,n:2。 不能在保持每段美观的前提下切成 1 段（整串不美观）。

数据范围

• $1 \le |s| \le 1000$
• $s$ 仅包含小写英文字母