Finding the lengths of the longest palindromic substrings for all prefixes of a given string

0
votes

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).

2
algorithmdata-structurespalindrome
what do you need to output as your answer? number of palindrome or longest palindrome substring - Sahan Dissanayaka
"we only need the lengths": plural? In the title you write that you only need the length of the longest palindrome, so that would be a singular result. - trincot
@trincot, Sorry for the confusion. We need it for all the prefixes. e.g. For the prefix "abab", it'll be 3. For "ababa", it'll be 5. - Neel J
@SahanDissanayaka, Need the lengths for all the prefixes. - Neel J
@trincot, even the title says that I need all the lengths. Please check the sample input / output I added in the question. - Neel J

2 Answers

0
votes

2nd option. Think about how manacher works. Each time it moves the right pointer it basically considers a new prefix. Keep track of the maximum value in the currently calculated part of the manacher's table values, in each iteration that is the length of the longest palindromic subsequence for the current prefix (ending on the right pointer). That takes O(n) time.

0
votes

I would suggest this solution:https://www.geeksforgeeks.org/longest-palindromic-substring-set-2/?ref=rp, its time complexity is O(N^2) and space complexity is O(1). But in your case you would need an array(maxArr) to hold length of maximum length substring for a prefix

Idea remains the same, you choose a center and find maximum length substring with that as center. Where the max substring will end, update the maximum length in array for that position. At last you might have some positions empty in the array(maxArr), those will hold the same values as the left position of them.