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

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 - Have 2 for loops for i = 1 to i less than array.length -1 for j=i+1 to j less than array.length - This way you can get substring of every possible combination from the array - Have a palindrome function which checks if a string is palindrome - so for every substring (i,j) call this function, if it is a palindrome store it in a string variable - If you find next palindrome substring and if it is greater than the current one, replace it with current one. - Finally your string variable will have the answer Issues: 1. This algo runs in O(n^2) time. Algo 2: - Reverse the string and store it in diferent array - Now find the largest matching substring between both the array - 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