一个字符串X被称为Y的anagram串，如果X是由Y的字符重新排序构成，不能移除或添加字符。比如”baba”, “abab”, “aabb”和”abba”是”aabb”的anagram串， “aaab”,”aab”和”aabc”则不是。

一个字符串X被称为Y的子串，如果X是从Y串中移除一些字符（0个字符也可以），并且剩下字符的顺序不变。比如”ac”,”abd”,”abcd”是”abcd”的子串，”ca”,”abb”,”abcde”则不是。

那么，一个字符串X称为Y的anagram子串，当且仅当存在一个字符串Z，X是Z的anagram串，Z是Y的子串。

对于一个长串S，罗老师想把他们分割成s1,s2,…,sn，也就是n个字符串，满足，当s1,s2,…,sn连接起来的时候刚好是S，同时，si是si+1的anagram子串(0<i<n)。 问题出来了，要满足这个条件，罗老师想知道，最多能分割成多少？

输入一行字符串S

输出最多分割成几份n

【样例说明】

可以分成{AB},{AB},{AB}

【数据规模和约定】

字符串长度范围 [1, 500]

字符串只包含[‘A’- ‘Z’]

AAXAAAABX

4

ABCDEFGHIJKL

1

ABBABBBBXZ

2

O(n^3)的算法

状态： dp[i][j]表示以[I,j]作为最后一段且合法，这样可以分成多少段,

转移： dp[i][k]合法, str[k+1, j]包含str[i, k]的字符，那么，str[k+1, j]可以接到str[i, k]后面增加一段，于是 dp[k+1][j]=max(dp[k+1][j], dp[i][k]+1);

阶段： 以初始位置i为阶段

       For i=0 to n-1

         For k=i+1 to n-1

            For j=k+1 to n-1

判断包含： 使用数组le[26]表示[i, k]记录每个字母的数量， 使用数组ri[26]表示[k+1, j]每个字母的数量是否大于等于[i, k]的。

答案： 最后答案为max(dp[0~n-1][n-1])