G面经prepare: Chucked Palindrome

 给定一个字符串，找出最多有多少个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);
    }

}