Today's algorithm of the day is the Longest Palindromic Substring:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
For example, let's say you were given the string "prefer". The output of the function should be "refer", because that is the longest substring of "prefer" which is a palindrome.
A palindrome is a word that is the same forwards and backwards--for example, "kayak", "level", and "noon". A substring is a continuous series of characters in a string--for example, "flow" is a substring of "flower". This problem is asking you to find the longest substring which is a palindrome in a given string.
Like most algorithms, there's many ways to solve this problem, but today I'll be solving it using the "expand around the center" method. The advantage of this method is that it uses constant space (O(1)). Although it uses O(n^2) time, the very little space it takes up is really interesting to me, so I wanted to give this approach a try.
I'll start by going over the approach behind this problem. Then I'll go on to code the solution in JavaScript. Finally, I'll illustrate how it works with an example.
Expanding Around the Center: Approaching the Problem
Let's say you're given the string "watt". To find the longest palindromic substring, you'd want to check all of the points in the string and see if the left and right of that point are identical. We can call all of those points "centers". You may think there are 4 centers in "watt", because it's 4 characters long--however, there are actually 7 centers in "watt", or 2n - 1 centers in a string of length n.
The reason why this is the case is that the space between each letter is also a "center"--that is, a substring may have an even number of characters, and so there is no single "middle" letter.
In the example of "watt", the longest substring is "tt", which means its center is the space between "t" and "t".
So in the expanding around the center approach, we'll iterate through each character in the given string, and will check not only the substring that has a center at each character, but also the substring that has a center between any two characters.
Solving for the Longest Palindromic Substring
To start solving this problem, we can account for edge cases. If the given string is less than a character long, we can simply return an empty string--there's no "substring" of an empty string.
function longestPalindrome(s) {
if (s.length < 1) return "";
//...
}
Now, we'll want to keep track of where the longest palindromic substring starts, and how long it is. We want to do this so that we can return that section of the inputted string at the end. We can set both of those values equal to 0 to start. We also can include a return statement at the bottom of the function to return the maximum substring. When called on a string, the method .substr() returns the the substring of a string. The first parameter passed in is the starting index of the substring you want to return, and the second (optional) parameter is the number of characters you want to return. Therefore, we can return the substring that starts at maxSubStart and is maxSubLength characters long.
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
//...
return s.substr(maxSubStart, maxSubLength);
}
Now, we'll want to walk through each character in s and perform checks on the substring at each step, so this is a good time to use a for-loop.
At each character in s, we'll want to check the substring which has a center at that character, and the substring which has a center between that character and the following character. We will write a helper function, expandAroundCenter to do this. expandAroundCenter will take in the string, the left parameter, and the right parameter. So, inside the for loop, we can call expandAroundCenter twice: once where left and right both equal the character we're currently on, and once where left equals the character we're currently on and right equals the next character in s.
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
for (let i = 0; i < s.length; i++) {
const lengthCenteredAtChar = expandAroundCenter(s, i, i);
const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
//...
}
return s.substr(maxSubStart, maxSubLength);
}
We'll get back to writing the helper function in a minute. For now, we can continue writing the function we're on. expandAroundCenter will return lengths, and we want to know which one is longer: the substring that's centered at the character, or the substring that's centered at the space. So, we can use Math.max() and pass in both of those lengths. Whichever one is longer, we can set equal to a variable, longestSubAtChar, which is the longest substring at each character.
Then, we'll want to see if the longest substring at the character we're on is longer than the maximum substring we've seen so far. To check this, we can write a conditional statement inside the for loop.
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
for (let i = 0; i < s.length; i++) {
const lengthCenteredAtChar = expandAroundCenter(s, i, i);
const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
if (longestSubAtChar > maxSubLength) {
//...
}
}
return s.substr(maxSubStart, maxSubLength);
}
If the current substring is longer than the maximum substring seen so far, we'll want to make the current substring the maximum. We'll do this by setting maxSubLength equal to longestSubAtChar.
We'll also want to change the starting point of the maximum substring so that we can return the correct substring at the end of the function. We can find the starting point by finding the halfway point of longestSubAtChar, and subtracting that from the character we're on.
In the example of "lava", the maximum substring is "ava", the center is "v" (index 2), and the start of that substring is "a" (index 1). In the example of "wattage", the maximum substring is "atta", the center is between "t" and "t" (index 2 and 3), and the start of that substring is "a" (index 1).
Finding half of the length of the substring means taking the length and subtracting 1, dividing that by 2, and performing Math.floor() on that calculation. Then, to find the start of the substring, subtract that number from i. (Note: you can see why you need to subtract 1 by looking at the example of "wattage". If we just divided 4 (the maxSubLength) by 2, we'd get 2. 2 (i) minus 2 is 0. The substring starts at 1, not 0. Subtracting one accounts for substrings of even lengths.)
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
for (let i = 0; i < s.length; i++) {
const lengthCenteredAtChar = expandAroundCenter(s, i, i);
const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
if (longestSubAtChar > maxSubLength) {
maxSubLength = longestSubAtChar;
maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
}
}
return s.substr(maxSubStart, maxSubLength);
}
We're now done with longestPalindrome(), and we just need to write the function which checks the substring at each center, expandAroundCenter(). expandAroundCenter() will take in the string, a left index, and a right index. We'll want to keep checking the letters at each left and right index to see if they're equal to each other as long as we're within the bounds of the string--so left has to be greater than or equal to 0, and right has to be less than the length of the string. We'll want to have a while loop continue to run so long as the characters at the left and right index are equal to each other, and we're still within the bounds of the string.
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
for (let i = 0; i < s.length; i++) {
const lengthCenteredAtChar = expandAroundCenter(s, i, i);
const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
if (longestSubAtChar > maxSubLength) {
maxSubLength = longestSubAtChar;
maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
}
}
return s.substr(maxSubStart, maxSubLength);
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
//...
}
//...
}
Inside the while loop, all we'll want to do is to continue to expand left and right. That means the left pointer should get smaller (go more toward the left), and the right pointer should get larger (go more toward the right).
Finally, once we're done executing the while loop (we're either out letters in s to check, or we've come to a point where the substring is no longer a palindrome we'll want to return the distance between left and right back to longestPalindrome(). To do this, we can just return right - left - 1.
function longestPalindrome(s) {
if (s.length < 1) return "";
let maxSubStart = 0;
let maxSubLength = 0;
for (let i = 0; i < s.length; i++) {
const lengthCenteredAtChar = expandAroundCenter(s, i, i);
const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
if (longestSubAtChar > maxSubLength) {
maxSubLength = longestSubAtChar;
maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
}
}
return s.substr(maxSubStart, maxSubLength);
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
Checking the Code With an Example
With that, we're done writing the solution to this problem. To check how this all works, I like walking through an example. I'll use the string "ABA". Even though the string is short, there are a lot of steps in this algorithm, so walking through it will take a bit of time. Nonetheless, I think it's super valuable to see how an example plays out.
We start with "ABA", and the maxSubStart and maxSubLength both automatically equal 0.
Now, we'll enter the for loop, and begin checking the character at index 0. We'll call expandAroundCenter() twice, once with left and right both at 0, and once with left at 0 and right at 1.
First we'll call expandAroundCenter where both left and right equal 0. That means the center is the "A" at index 0. Since left is greater than or equal to 0, right is less than the length of the string, and the value at left and right are equal, we'll expand the center.
Now, left is -1 and right is 1. The while loop, however, is no longer true. That means that we won't enter the loop, and will return right - left - 1, which equals 1.
= 0; right < s.length; s[0] === s[0]". Beneath that is "left = -1; right = 1". Beneath that is the string "ABA", with the same purple vertical line in the middle of the first "A", but now the purple horizontal line extends before the "A" to the blank space, and also covers the "B". Beneath that is "left >= 0" with a red "X" next to it. Beneath that is "return right - left - 1 --> 1 - (-1) - 1 --> 1"."/>
Now we'll call expandAroundCenter with left = 0 and right = 1. That means the center is between "A" and "B". Since the character at the left index does not equal the character at the right index, we won't enter the while loop, and will return 0.
= 0; right < s.length; s[0] === s[1]", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 1 - 0 - 1 --> 0"."/>
We're back to our function. We can compare the return values of both calls to expandAroundCenter, and since 1 > 0, longestSubAtChar will equal 1. The current maximumSubLength is 0, and since 1 > 0, the maxSubLength will equal 1. We can set maxSubStart equal to 0, as that's the index that the maximum palindromic substring ("A") started at.
"expandAroundCenter(”ABA”, 0, 0) = 1" written in purple and "expandAroundCenter(”ABA”, 0, 1) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 1; maxSubLength = 0; longestSubAtChar > maxSubLength". Beneath that is "maxSubLength = longestSubAtChar = 1; maxSubStart = 0 - Math.floor((1 - 1)/2) = 0.""/>
We can move on to checking "B" at index 1. We'll call expandAroundCenter twice, once where the center is the letter "B", and once where the center is the space between "B" and the next letter "A".
First we'll check where the center is "B". Left is 1 and right is 1, which are both inside the bounds of the string, and "B" === "B", so we can enter the while loop. We will expand from the center, decrementing left, and incrementing right.
Now left is 0 and right is 2. Both of these values are inside of the bounds of the string, and the characters at these values are equal to each other ("A" === "A"), so we can go through the while loop again.
Now left is -1 and right is 3. Since left is no longer greater than or equal too 0, we don't even have to check the rest of the conditional, because we know we can't enter the while loop. We will return 3 back to the function.
= 0; right < s.length; s[1] === s[1]". Beneath that is "left = 0; right = 2". Beneath that is the string "ABA", with the same purple vertical line in the middle of the "B", but now the purple horizontal line extends to the left and right to cover the full string, "ABA". Beneath that is "left >= 0; right < s.length; s[2] === s[0]". Beneath that is "left = -1; right = 3". Beneath that is the string "ABA", with the same purple vertical line in the middle of the "B", but now the horizontal line extends to the white space to the left and right of the string. Beneath that is "left >= 0" with a red "X" next to it. Beneath that is "return right - left - 1 --> 3 - (-1) - 1 --> 3"."/>
We'll check where the center is the space between "B" and "A". Left is 1 and right is 2. However, since "B" does not equal "A", we can't enter the while loop, so we'll return 0 to the function.
= 0; right < s.length; s[1] === s[2]", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 2 - 1 - 1 --> 0"."/>
Now we can compare the return values of both calls to expandAroundCenter. Since 3 is larger than 0, it's the longestSubAtChar. Since 3 is larger than the previous maximum substring (1), 3 becomes the new maxSubLength, and the maxSubStart is 0.
"expandAroundCenter(”ABA”, 1, 1) = 3" written in purple and "expandAroundCenter(”ABA”, 1, 2) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 3; maxSubLength = 1; longestSubAtChar > maxSubLength". Beneath that is "maxSubLength = longestSubAtChar = 3; maxSubStart = 1 - Math.floor((3 - 1)/2) = 0.""/>
We can move to the last letter of the string, "A", and i = 2. We'll again call "expandAroundCenter" twice, once for each potential "center".
First we'll look at the substring which is centered around A. Left = 2 and right = 2 (both inside the confines of the string), and "A" === "A", so we can enter the while loop and expand from the center.
Now left is 1 and right is 3. Even though left is greater than 0, right is outside the confines of the string, so we can't enter the while loop. We'll return 1 to the function.
= 0; right < s.length; s[2] === s[2]". Beneath that is "left = 1; right = 3". Beneath that is the string "ABA", with the same purple vertical line in the middle of the first "A", but now the purple horizontal line extends before the "A" to the "B", and to the blank space to the right. Beneath that is "left >= 0; right < s.length" with a red "X" next to the last clause. Beneath that is "return right - left - 1 --> 3 - 1 - 1 --> 1"."/>
We'll now call expandAroundCenter with left = 2 and right = 3. Since 3 is larger than the length of the string, we won't enter the while loop. We can return 0 to the function.
= 0; right < s.length", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 3 - 2 - 1 --> 0"."/>
Back in the function, we can compare the two longest substrings at this index in the string. The longest one is 1 character long (the letter "A"). Since 1 is not larger than the existing maximum substring length, we won't change the maximum substring values.
Since we're done checking the characters of the string, we can return the maximum substring--it starts at index 0, and is three characters long, which is "ABA".
"expandAroundCenter(”ABA”, 2, 2) = 1" written in purple and "expandAroundCenter(”ABA”, 2, 3) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 1; maxSubLength = 3; longestSubAtChar > maxSubLength", with a red "X" next to the last clause. Beneath that is "return 'ABA'.substr(0, 3); return 'ABA'"."/>
--
Please let me know if you have any questions or alternative solutions to this problem!
Top comments (6)
Hi. A really a nice approach! I was wondering about the time complexity. I sometimes find it difficult to determine the time complexity of an algo with certainty, even the ones i write. Could you please elaborate on that... I wrote a different algorithm, just trying to judge if this one has a better complexity than mine, because mine does not eally perform that efficiently:
Hi Saloni,
In the algorithm I used above, the reason its time complexity is O(n^2) can be found by looking at the for loop. The for loop examines each element of
s, which takes O(n) time (n being the length ofs). Then, inside the for loop, I callexpandAroundCenter. InexpandAroundCenter, I'm again traversing the string (even though I may just be looking at one character, I could be looking at the entire string again, like in the case of checking the "B" in "ABA"). That would take, at most, O(n) time. Because expandAroundCenter is nested inside the for loop, that means it takes a total of O(n^2) time.In your function, you have a while loop, which goes from the end of the string to the start. In other words, you could write
while (len>0) {...asfor (let i = len; i > 0; i--) {. So in that line, that's O(n). Then inside the loop, you have another for loop. If you think about the example of "AAAA", the first time through the while loop, len would = 4, and inside the for loop, str would = "AAAA". Then,isPalindromwould be called, and it'd start at either end, and end up checking every character of the string, which is also O(n). So, it looks like overall the time would be O(n^2).Thank you for the help with time complexity Alisa! Also, your post is very well explained. So thank you for that as well :)
Given a strings and an integer D. The task is to determine the length of the longest palindromic string P that can be prepared using D distinct characters of string S such that the frequency of any character C in string P is at most the frequency of the same character in the string S.
Nice post, made me think if there are asymptotically faster options. The best I could do was O(n log n) by binary searching and doing polymorphic hashing, which is only probibalistic. It would only give false positives though, so you could check. You did specify a max length, though, so O(n^2) is maybe even faster in this case, if the loops are unrolled and cache is good or something.