Write a function that returns the longest palindrome in a given string. e.g "ccddcc" in the string "
- by Learner
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
