给定一个字符串，找出最多有多少个chunked palindrome, 正常的palindrome是abccba, chunked palindrome的定义是：比如volvo, 可以把vo划分在一起，(vo) (l) (vo)，那么它是个palindrome。求实现返回最大的chunk 数量。 比如aaaaaa可以是(aaa)(aaa), 但是最大chunk数量应该是(a)(a)(a)(a)(a)(a)为6
这就是一个greedy的问题，从string的两边开始，用i和j记录当前scan到的位置，用prev_i和prev_j记录上一次找到chunk的i和j的位置的下一个字符。最后扫到中间判断一下有无多余的chunk。
时间复杂度为O(N^2), 内层string.equals 有O（N）复杂度
package ChunkedPalindrome;
public class Solution {
public int countChunk(String str) {
if (str==null || str.length()==0) return 0;
int sum = 0;
int l=0, r=str.length()-1;
int preL = l, preR = r;
while (l < r) {
String left = str.substring(preL, l+1);
String right = str.substring(r, preR+1);
if (left.equals(right)) {
preL = l+1;
preR = r-1;
sum += 2;
}
l++;
r--;
}
if (preL <= preR) sum+=1;
return sum;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
int res = sol.countChunk("aaaaaa");
System.out.println(res);
}
}