One traditional question is to find the longest palindrome in a string. This has 3 ways to solve:
1. For each element, use 2 pointers to move to left and right. And find the furthest it can move.
2. Use lcs to find the longest common substring between string and reversed-string. Take “abccbd” as example, we find LCS of “abccbd and “dbccba”.
3. Use dynamic programming, this way is similar to junmin’s post to find the longest parenthesis. link
There is another quesiton which can be developed. It is find the minimum number that we partition the string to all palindrome string. We can similar way to above method 3 to solve this problem.
We use array. arr[i][j] is the minimum palindrom partition number. For element where i=j, we set arr[i][j]=1. For example if we want to calculate arr[3][6]. If arr[2][5] is 1, and str[3]==str[6], then we know str[3]…str[6] is a palindrome. Or arr[3][6] = min {arr[3][3]+arr[4][6], arr[3][4]+arr[5][6], arr[3][5]+arr[6][6]}
After we built this array, arr[0][length-1] will be the answer.
check my code on github: link