Longest Palindromic Substring
Medium1-D dynamic programming
Given a string s, return its longest substring that reads the same forwards and backwards. A substring is a run of characters next to each other in s.
When several substrings share the longest length, return any one of them. Upper and lower case letters count as different characters.
Examples
Input: s = "rotorcar" Output: "rotor"
rotor reads the same both ways.
Input: s = "abccbx" Output: "bccb"
An even-length palindrome: its centre is the gap between the two c’s.
Constraints
1 ≤ s.length ≤ 1000sholds English letters and digits only.
Stuck?
Hint 1
Every palindrome grows outwards from a centre. That centre is either one character (odd length) or the gap between two characters (even length).
Hint 2
For each of the 2n - 1 centres, expand while the characters on both sides match, and remember the longest stretch you reach.
The idea
Every palindrome reads the same outwards from its middle, and that middle is either one letter or the gap between two equal letters. So try each letter and each gap between neighbours as a middle, and widen a window from it while its two ends match. That is 2n - 1 middles, each widened at most n times, so the search takes O(n²) time and keeps only the best answer so far.
Time O(n²)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
The best palindrome so far is kept as where it starts and how long it is. Any single character is a palindrome, so the best starts as the first character, with length 1.
function longestPalindrome(s) { let start = 0; let length = 1; const grow = (left, right) => { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } if (right - left - 1 > length) { start = left + 1; length = right - left - 1; } }; for (let i = 0; i < s.length; i++) { grow(i, i); grow(i, i + 1); } return s.slice(start, start + length);}The trap
Growing only from single characters finds every odd-length palindrome, so it looks complete and passes any string whose longest palindrome has a middle letter. An even-length palindrome has no middle letter: its centre is the gap between two equal letters, and a window that starts on one character never covers it whole. Strings whose longest palindrome has even length get a shorter answer.
function longestPalindrome(s) { let best = s[0]; for (let i = 0; i < s.length; i++) { let left = i; let right = i; while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } if (right - left - 1 > best.length) best = s.slice(left + 1, right); } return best; // only odd-length centres}