Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Example
Input: s = "babad"
Output: "bab:
Note: "aba" is also a valid answer.
In order to solve this problem we first need to understand what a palindrome is. A palindrome is a word that is the same spelled backward and forward. An example of a palindrome would be the word radar. Now that we have the english out of the way let's take a look at how we would solve the problem. The first solution that comes to mind would be to loop through the string and build up all the substrings from within it. We can then test each of the substrings to determine if they are palindromes. All that would be left would be to find the longest of those substrings and return it. Finding all the substrings of the string with loops would be O(n2) time. That wouldn't be bad if that's where we stopped. Unfortunately we still have to determine if the substrings are palindromes. That's an additional loop taking us to O(n3). Let's work through to see if we can find a better solution. As always we will start with the skeleton problem.
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome = function(s) {
}
We will need some way to keep track of the longest substring that is a palindrome, so we will start by setting up a variable to track that. It will be an array that will store the starting and ending index of the substring in the input string. We can initialize it with the indices of 0 and 1 since we know that the first letter is going to be a palindrome.
const longestPalindrome = function(s) {
let maxLongest = [0, 1]
}
For our solution we can iterate over the letters in the string and check for the longest palindrome that is centered around that letter. We can just use a for loop fo that.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
}
}
Let's stop for a minute and think about palindromes again. We mentioned before that radar would be a palindrome. As you can see the palindrome is centered around the letter d. We can check each letter of the input string to see if it is the center of a palindrome and if so what is the maximum length of a palindrome centered around that letter. Let's pull that out into a separate function call. It will take in the input string and the index of its adjacent letters.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
}
All we need to do in there is compare the letters at the adjacent indices and if they are equal move the indices over to the next adjacent letter. We would continue to do this until our lower index or upper index goes outside the bounds of our string. At the end we will return a tuple with the start and ending index of the longest substring that has passed the test.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}
We can add that to our loop and check that for each letter in the string.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
const currentLength = getLongestPalindromeFrom(s, i - 1, i + 1);
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}
We are now finding every palindrome that is centered on each letter of the input string. Before we move on we should revisit our definition of palindrome. Back to our original example we would find the palindrome radar when we encountered the letter d in that word. But what about the palindrome deed? We would completely miss that in our current iteration. We need to figure out a way to account for those as well. Fortunately we have a function that we can pass in indices to. If we pass in the current index and the previous index we would change the palindrome to be centered around the space between the two letters vs the current letter of the loop.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
const currentLengthAroundLetter = getLongestPalindromeFrom(s, i - 1, i + 1);
const currentLengthAroundSpace = getLongestPalindromeFrom(s, i - 1, i);
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}
That will allow us to find both the palindromes centered around all the letters as well as the palindromes centered around all the spaces between the letters. All that is left to do now is to compare the lengths of them all and keep track of the longest one. First we compare the lengths of the longest palindrome centered around the letter and the longest palindrome centered around the space before the letter.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
const currentLengthAroundLetter = getLongestPalindromeFrom(s, i - 1, i + 1);
const currentLengthAroundSpace = getLongestPalindromeFrom(s, i - 1, i);
const longest = currentLengthAroundLetter[1] - currentLengthAroundLetter[0] >
currentLengthAroundSpace[1] - currentLengthAroundSpace[0] ?
currentLengthAroundLetter : currentLengthAroundSpace
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}
Finally we just need to compare that to the longest palindrome we have seen so far. If it's larger we need to assign it to our maxLongest variable.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
const currentLengthAroundLetter = getLongestPalindromeFrom(s, i - 1, i + 1);
const currentLengthAroundSpace = getLongestPalindromeFrom(s, i - 1, i);
const longest = currentLengthAroundLetter[1] - currentLengthAroundLetter[0] >
currentLengthAroundSpace[1] - currentLengthAroundSpace[0] ?
currentLengthAroundLetter : currentLengthAroundSpace;
maxLongest = maxLongest[1] - maxLongest[0] >
longest[1] - longest[0] ? maxLongest : longest;
}
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}
We can now just return the slice of the input string based on the indies we have stored that represent the longest palindrome substring.
let longestPalindrome = function(s) {
let maxLongest = [0, 1]
for (let i = 1; i < s.length; i++) {
const currentLengthAroundLetter = getLongestPalindromeFrom(s, i - 1, i + 1);
const currentLengthAroundSpace = getLongestPalindromeFrom(s, i - 1, i);
const longest = currentLengthAroundLetter[1] - currentLengthAroundLetter[0] >
currentLengthAroundSpace[1] - currentLengthAroundSpace[0] ?
currentLengthAroundLetter : currentLengthAroundSpace;
maxLongest = maxLongest[1] - maxLongest[0] >
longest[1] - longest[0] ? maxLongest : longest;
}
return s.slice(maxLongest[0], maxLongest[1])
}
function getLongestPalindrome(string, leftIdx, rightIdx) {
while (leftIdx >= 0 && rightIdx <= string.length) {
if (string[leftIdx] !== string[rightIdx]) {
break
}
leftIdx--
rightIdx++
}
return [leftIdx + 1, rightIdx]
}