I've gone through the problem of finding the longest palindromic substring, but this is different.
Given a String like "ababa", the lengths of the longest palindromic substrings for *all* the prefixes will be as per below -

* "a" : "a" (Length 1)
* "ab" : "a" or "b" (Length 1)
* "aba" : "aba" (Length 3)
* "abab" : "aba" or "bab" (Length 3)
* "ababa" : "ababa" (Length 5)

Here's the sample input / output ->

* **Sample Input**: "ababa"
* **Sample Output**: 1 1 3 3 5

I thought about a couple of solutions -

1. Find out all the palindromic substrings of the given string (O(N^2) using expanding around centre approach) and then for each prefix, find out if it contains the substrings (sorted in desc order of lengths). This seems to be worse than O(N^3).
2. For each prefix, find the longest palindromic substring using Manacher's algorithm (O(N)). There will be N prefixes, so this is O(N^2).

We need only the lengths and not the actual palindromes. Is there any easier / better (in terms of of runtime complexity) way that I'm missing out on?

Update : We need the lengths (of longest palindromic substrings) for all the prefixes of the string (like in the example above).