Longest palindrome in a string
You have it backwards - if you output the "odd" palindromes (with your fix) you'll find they're actually even-length.
Imagine "noon", starting at the first "o" (left and right). That matches, then you move them both - now you're comparing the first "n" to the second "o". No good. But with the fix, you start out comparing both "o"s, and then move to both "n"s.
Example (with the var oddPal = centeredPalindrome(i-1, i);
fix):
var longestPalindrome = function(string) {
var length = string.length;
var result = "";
var centeredPalindrome = function(left, right) {
while (left >= 0 && right < length && string[left] === string[right]) {
//expand in each direction.
left--;
right++;
}
return string.slice(left + 1, right);
};
for (var i = 0; i < length - 1; i++) {
var oddPal = centeredPalindrome(i, i + 1);
var evenPal = centeredPalindrome(i, i);
if (oddPal.length > 1)
console.log("oddPal: " + oddPal);
if (evenPal.length > 1)
console.log("evenPal: " + evenPal);
if (oddPal.length > result.length)
result = oddPal;
if (evenPal.length > result.length)
result = evenPal;
}
return "the palindrome is: " + result + " and its length is: " + result.length;
};
console.log(
longestPalindrome("nan noon is redder")
);
devdropper87
Updated on June 11, 2022Comments
-
devdropper87 almost 2 years
I wrote the following function to find the longest palindrome in a string. It works fine but it won't work for words like "noon" or "redder". I fiddled around and changed the first line in the
for
loop from:var oddPal = centeredPalindrome(i, i);
to
var oddPal = centeredPalindrome(i-1, i);
and now it works, but I'm not clear on why. My intuition is that if you are checking an odd-length palindrome it will have one extra character in the beginning (I whiteboarded it out and that's the conclusion I came to). Am I on the right track with my reasoning?
var longestPalindrome = function(string) { var length = string.length; var result = ""; var centeredPalindrome = function(left, right) { while (left >= 0 && right < length && string[left] === string[right]) { //expand in each direction. left--; right++; } return string.slice(left + 1, right); }; for (var i = 0; i < length - 1; i++) { var oddPal = centeredPalindrome(i, i); var evenPal = centeredPalindrome(i, i); if (oddPal.length > result.length) result = oddPal; if (evenPal.length > result.length) result = evenPal; } return "the palindrome is: " + result + " and its length is: " + result.length; };
UPDATE: After Paul's awesome answer, I think it makes sense to change both variables for clarity:
var oddPal = centeredPalindrome(i-1, i + 1); var evenPal = centeredPalindrome(i, i+1);