You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

印刷字符串

题目描述

最近小白兔从小黑兔那里接到了一个在纸上印刷字符串的工作。为了完成这项工作，小白兔决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。

小白兔发现，同一个位置的相同字符可以印多次。例如：用 aba这个印章可以完成印制ababa的工作（中间的a被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用aba这个印章不可以完成印制abcba的工作。

因为刻印章是一个不太容易的工作，小白兔希望印章的字符串长度尽可能小。所以它找到了你，想让你算出来印章最少要刻多长。

输入格式

输入一个长度为n的非空字符串，代表要在纸上印的字符。

输出格式

输出一个整数，代表印章上字符串长度的最小值。

样例 #1

样例输入 #1

ababbababbabababbabababbababbaba

样例输出 #1

8

提示

印章为 ababbaba。

印制过程如下：

ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba

数据范围

对30%的数据，$1\le n\le 100$。

对100%的数据， $1\le n \le 5 \times 10^5$，字符串中只有小写字母。