algorithm - Write a function that returns the longest palindrome in a given string

Question

e.g "ccddcc" in the string "abaccddccefe"

I thought of a solution but it runs in O(n^2) time

Algo 1:

Steps: Its a brute force method

1. Have 2 for loops
   for i = 1 to i less than array.length -1
   for j=i+1 to j less than array.length
2. This way you can get substring of every possible combination from the array
3. Have a palindrome function which checks if a string is palindrome
4. so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
5. If you find next palindrome substring and if it is greater than the current one, replace it with current one.
6. Finally your string variable will have the answer

Issues: 1. This algo runs in O(n^2) time.

Algo 2:

1. Reverse the string and store it in diferent array
2. Now find the largest matching substring between both the array
3. But this too runs in O(n^2) time

Can you guys think of an algo which runs in a better time. If possible O(n) time

Answer 1

You can find the the longest palindrome using Manacher's Algorithm in O(n) time! Its implementation can be found here and here.

For input String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" it finds the correct output which is 1234567887654321.