I’ve provided my solution below using Java, it runs in O(n) time, or linear time. Explanation of the algorithm will follow. Please excuse the encoding errors in the code; < &rt; and & will need to be replaced with the correct corresponding characters
private String palindrome(String word) {
char[] word_c = word.toCharArray();
int maxIndex = 0;
int[] lengths = new int[word.length()];
lengths[0] = 1;
for (int i = 1; i < word.length(); i++) {
lengths[i] = 1; // Prep for each iteration: every char is a palindrome of itself
if (word_c[i] == word_c[i-1]) { //Handles the "Even" cases"
lengths[i] = 2;
}
/*
* First verify our index is not out of bounds
* Then check if the character on the far side of the concentric palindrome
* is the same. If so our palindrome grows by 2 characters.
*/
if (i-1 > 0 && i-lengths[i-1]-1 >= 0 && //Check index bounds
word_c[i] == word_c[ i - lengths[i - 1] - 1 ]) {
lengths[i] = lengths[i-1] + 2;
}
//Maintain what is the longest palindrome
if (lengths[i] > lengths[maxIndex]) {
maxIndex = i;
}
}
int startIndex = maxIndex - lengths[maxIndex] + 1;
int endIndex = startIndex + lengths[maxIndex];
return word.substring(startIndex, endIndex);
}Analysis:
The essential concept that is overlying the algorithm is the concept of maintaining a collection of values that indicate how long the palindrome that precedes each character is as we iterate through the given string from left to right. So, given the string “aba” and starting on the left (position 0) the palindrome that precedes “a” is of length 1 because “a” is the same forwards and backwards. Next we iterate to the next position, “b“. We first check the letter preceding it to see if it is equal. We do this because not all palindromes are of odd length. “bb” is just as valid of a palindrome as “aba“. Once we determine that they are or are not equal we use the length of the preceding palindrome to determine if we need to extend our search. Less technically what we’re doing is checking the position prior to our current position to see if it is the endpoint to a palindrome, and if so we attempt to see if the current position extends the already established palindrome. While looking at “b” we look back at “a” to determine that it is the end of a palindrome of length 1 so we would want to look 1 place beyond “a” to see if there is a matching character. Fortunately we do a check to ensure we don’t hit an ArrayOutOfBoundsException.
We conclude that “ab” is an invalid palindrome and maintain that “b” is a palindrome of length 1.
Again we iterate and reach the second “a” in our string. Like before we first check it to the preceding character, “b” and happily conclude that “ba” is not a good palindrome. We then look at the length of the palindrome terminated at the position to our left, see it is a palindrome of length 1 and look 1 place to its left to see if there is an equal character. Quite simply we establish that “a” is equal to “a“. Our palindrome is now equal to the length of the preceding palindrome plus the addition of two characters (one to the front, one to the end).
We finish this iteration by checking the length of the current palindrome against the length of the previously longest palindrome and store the index.
Once finish our entire iteration of the string we are left with an array of palindrome lengths, our example would have an array that looks like { 1, 1, 3 }. We take the knowledge that index 2 has the longest palindrome of length 3 and use a bit of grade school math to pull the sub-string from our initial submission.
Down to the Meat: Line by Line.
Variables:
1) Starting from the top we see the variable declarations. I’ve taken the String provided and dumped it to an array of characters because that is simpler to work with than sub-stringing each iteration.
2) The int variable that will store the location of the terminating character to our longest palindrome.
3) Our array of palindrome lengths. This is the true meat of our algorithm. We establish index 0 to equal one because, as explained previously, any single letter can be a palindrome of itself.
The Algorithm:
4) The for loop runs from index 1 to the last character of the array. This ensures we do one complete pass over the entire string but skips the first character because there is no reason to be doing any work on a character that cannot be a palindrome longer than 1.
5) The first if statement checks the equality between the current character and the preceding character directly. This establishes even length palindromes like “abba” by setting the palindrome length to 2.
6) The next if statement first establishes that we are not accessing an invalid index during our search (such as -1) and then uses a bit of fancy trickery to determine if the current character belongs to a palindrome. The easiest way to understand this set up process is to recognize that as we work from left to right on the palindrome we are setting up a set of palindromes that are contained within the larger palindromes. In my high level example previously I explained how this works but if you visualize the palindrome abcdcba we know that the entire string is a palindrome but we mustn’t neglect the fact that “bcdcb“, “cdc” and “d” are all palindromes that are contained within the larger palindrome.
Having said that, if you’re still with me you can now look at the last clause of the if statement, word_c[i] == word_c[ i - lengths[i - 1] – 1 ] and see that we are comparing the current character to the one far side of the palindrome terminated at the last character. Using the abcdcba example again, while we’re observing the second “b” of the string we are comparing it to the letter on the far side of the inner palindrome “cdc” which also happens to be “b“. With this equality established we then add 2 to the length of the last palindrome’s length and continue.
7) If the new palindrome is longer than the last previously known palindrome we can now store a new index. This is useful for strings like “abaxcdefedc” where there are more than one palindrome in the string that are not co-centered.
8 ) Finally we need to do a bit of set up to strip the sub-string from the initial word and return it. The Java substring() routine needs a start index and an end index unlike some languages which use a start index and a length; so modify accordingly if you’re using such a language. The startIndex is where the palindrome started. We know where it ends, and how long it is so taking the end point, subtracting its length and then adjusting by 1 we get the starting index.
9) The end index is quite simply the startIndex plus the length of the palindrome.
10) Finally we return the result.
Conclusion:
Using Big-O notation to determine run-time we see that it executes in Linear time O(n). For those unfamiliar with the run-times of algorithms what this basically means is if we were to double the length of the string we’re searching our algorithm would take twice as long to execute. Other palindrome algorithms often execute in O(n^2) meaning they’d quadruple in time for an input string of twice the length.
The reason I’ve written this is because I’ve seen a few solutions posted online attempting to help people come up with the coveted solution but all fall short in one method or another. Some authors fail entirely at variable naming conventions while others provide no documentation to the solutions and even further I’ve seen a few cryptic solutions that fail to execute on all test cases. Beyond that a student or individual seeking direction can really struggle if there is no documentation associated with the code if it is in an unfamiliar language.
If you have any questions or need a better explanation please let me know!
