Check out this brilliant solution:
https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp
My first solution was a O(n^2) typical DP boiler-plate code. The key is, that solution is too generalized. With given char as the ending char in such a string, its previous chars are the same.