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
I was asked this question recently. Here's the solution I [eventually] came up with. I did it in JavaScript because it's pretty straightforward in that language.
The basic concept is that you walk the string looking for the smallest multi-character palindrome possible (either a two or three character one). Once you have that, expand the borders on both sides until it stops being a palindrome. If that length is longer than current longest one, store it and move along.
This could definitely be cleaned up and optimized a little more, but it should have pretty good performance in all but the worst case scenario (a string of the same letter).
Here i have written a logic try it :)
my solution is :
The Algo 2 may not work for all string. Here is an example of such a string "ABCDEFCBA".
Not that the string has "ABC" and "CBA" as its substring. If you reverse the original string, it will be "ABCFEDCBA". and the longest matching substring is "ABC" which is not a palindrome.
You may need to additionally check if this longest matching substring is actually a palindrome which has the running time of O(n^3).
I have written the following Java program out of curiosity, simple and self-explanatory HTH. Thanks.
Following code calculates Palidrom for even length and odd length strings.
Not the best solution but works for both the cases
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE