Solution to the longest palindromic substring problem
Overview:
Longest Palindromic Substring is a computer science problem, where you have to find the longest contiguous substring, which should also be a palindrome. For example, the longest palindromic substring for a string “banana” would be “anana” , where the substring is a palindrome, and also the longest of all palindromes in the string.
I came across this problem on LeetCode and this post is an attempt to explain the solution to you. Hopefully, it will help you understand and solve the problem and help me understand it better.
Question:
Given a string s , find the longest palindromic substring in s .
For example, for the input “babad” , the output would be “bab” . For the input “cbbd” , the output would be “bb” .
Brute Force:
The first approach that came to my mind was the brute force solution. It seemed pretty straight forward considering all we had to do was:
- Loop over the string for the starting index of each substring.
- Loop over the string again and get ending indexes for all the possible substrings.
- Check if each substring is a palindrome.
- Store the longest palindrome.
Yeah, sounds good doesn?t work.
Since we are looping for the starting index of every substring and looping again for the ending index for each starting index, the time complexity of the algorithm will be O(n). We also need to implement an algorithm to check if a substring is a palindrome, which alone would have the time complexity of O(n) making the cumulative time complexity of the entire algorithm o(n). It seems plausible in theory, but our computers don?t have that kind of patience.
Expand Around Center:
Every palindrome is basically a mirror image around a central character. For example , “anana” is a mirror with the center “a” . Also, a palindrome could have two characters at their center instead of just one. For example, in the palindrome “abba” , the center is “bb” . Using these facts, we can write an expand function, that will return the longest possible palindrome with each character in the string as the center for a possible palindrome.
Assuming the expand function was available to us, all we need to do next is to loop over the string once and find the largest possible palindrome for each character at the center. We also need to initialize the longest palindrome as an empty string. If the current palindrome has a greater length that the current longes palindrome, then we can set it as the current longest palindrome. Also, since there could be two centers in a palindrome, we will have to repeat the process for the next character that follows the current character.
const longestPalindrome = s => { let longest = s.substring(0, 1) for(let i = 0; i < s.length; i++) { let temp = expand(s, i, i) if(temp.length > longest.length) { longest = temp } temp = expand(s, i, i + 1) if(temp.length > longest.length) { longest = temp } } return longest}
Also, to shorten the process when the given string is empty or is a single character, we can just return the string and not go through the program at all.
const longestPalindrome = s => { if(!s || s.length <= 1) { return s } let longest = s.substring(0, 1) for(let i = 0; i < s.length; i++) { let temp = expand(s, i, i) if(temp.length > longest.length) { longest = temp } temp = expand(s, i, i + 1) if(temp.length > longest.length) { longest = temp } } return longest}
Finally, we need to write the expand function. The function will take three arguments:
- s: the given string
- start: the index of the current character in the string
- end: the index of the current character first, and the index of the next character for a possible center with two characters
The function will execute a while loop where the loop will stop if the indexes are expanded beyond the length of the string or 0. If the start and end characters are equal, then we have a palindrome.
Next, we need to expand it. For the expansion around the center, we will decrement the start and increment the end indexes and execute the while loop again. While the start and end characters are equal, the palindrome can keep expanding. When it’s not, we will exit the while loop and return a substring of the string with the expanded start and end indexes.
const expand = (s, begin, end) => { while(begin >= 0 && end <= s.length – 1 && s[begin] === s[end]) { begin– end++ } return s.substring(begin + 1, end)}
Solution:
This is the solution that worked for me. It has a time complexity of O(n2) and a space complexity of O(n). If you want to first try solving the problem on your own, take your time and come back if it seems impossible to solve.
const longestPalindrome = s => { if(!s || s.length <= 1) { return s } let longest = s.substring(0, 1) for(let i = 0; i < s.length; i++) { let temp = expand(s, i, i) if(temp.length > longest.length) { longest = temp } temp = expand(s, i, i + 1) if(temp.length > longest.length) { longest = temp } } return longest}const expand = (s, begin, end) => { while(begin >= 0 && end <= s.length – 1 && s[begin] === s[end]) { begin– end++ } return s.substring(begin + 1, end)}
In a nutshell:
Longest Palindromic Substring is a very popular problem in computer science. It has a number of generic algorithms you can use to solve it. We discussed the Brute Force solution and implemented the Expand Around Center algorithm with O(n) time complexity and O(n) space complexity. There is a solution that uses the principles of Dynamic Programming that uses O(n) time complexity and O(n) space complexity. There is also an algorithm with O(n) runtime, called the Manacher?s Algorithm. Please feel free to check them out here on LeetCode and apply the algorithm that best fits your needs.
Happy Problem Solving!
