title: Finding the lengths of the longest palindromic substrings for all prefixes of a given string
body: <p>I've gone through the problem of finding the longest palindromic substring, but this is different.
  Given a String like &quot;ababa&quot;, the lengths of the longest palindromic substrings for <em>all</em> the prefixes will be as per below -</p>
  <ul>
  <li>&quot;a&quot; : &quot;a&quot; (Length 1)</li>
  <li>&quot;ab&quot; : &quot;a&quot; or &quot;b&quot; (Length 1)</li>
  <li>&quot;aba&quot; : &quot;aba&quot; (Length 3)</li>
  <li>&quot;abab&quot; : &quot;aba&quot; or &quot;bab&quot; (Length 3)</li>
  <li>&quot;ababa&quot; : &quot;ababa&quot; (Length 5)</li>
  </ul>
  <p>Here's the sample input / output -&gt;</p>
  <ul>
  <li><strong>Sample Input</strong>: &quot;ababa&quot;</li>
  <li><strong>Sample Output</strong>: 1 1 3 3 5</li>
  </ul>
  <p>I thought about a couple of solutions -</p>
  <ol>
  <li>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).</li>
  <li>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).</li>
  </ol>
  <p>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?</p>
  <p>Update : We need the lengths (of longest palindromic substrings) for all the prefixes of the string (like in the example above).</p>