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.
Constraints:
- 1 <= s.length <= 1000
- s consist of only digits and English letters (lower-case and/or upper-case)
Examples:
Input: "babad"
Output: "bab"
Explanation: "bab" is a palindromic substring and the longest one.
Input: "cbbd"
Output: "bb"
Explanation: "bb" is a palindromic substring and the longest one.
Solutions
Expand Around Center
Time: O(n^2)Space: O(1)
The idea is to expand around the center of the palindrome. We consider two types of palindromes: odd length and even length. For odd length, the center is a single character. For even length, the center is between two characters.
function longestPalindrome(s) {
let longest = '';
for (let i = 0; i < s.length; i++) {
let palindrome1 = expandAroundCenter(s, i, i);
let palindrome2 = expandAroundCenter(s, i, i + 1);
longest = longest.length > palindrome1.length ? longest : palindrome1;
longest = longest.length > palindrome2.length ? longest : palindrome2;
}
return longest;
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.slice(left + 1, right);
}
Follow-up:
What if the input string is very large and we need to find all palindromic substrings?
