A palindrome reads the same forwards and backwards, like level or abba. A substring is a
run of consecutive characters.
Given a string s, return its longest substring that is a palindrome. If several are equally
long, return the one that starts first.
Example 1
- Input
- s = "cabbad"
- Output
- "abba"
abba reads the same both ways, and nothing longer does.Example 2
- Input
- s = "abcd"
- Output
- "a"
a starts first.Example 3
- Input
- s = "abacdc"
- Output
- "aba"
aba and cdc are both 3 long; aba starts first.Constraints
sholds 1 to 1000 characters, each a lowercase letter or a digit.
Show the pattern
Dynamic programming (2D), Two pointers
Whether `s[i..j]` reads the same both ways depends on its two ends matching and on `s[i+1..j−1]`: a question about a pair of positions, answered from a shorter pair. That is a 2D table, or the same idea run outwards from each centre.
See dynamic programming (2d) in a visualiserShow the approach
As a table: pal[i][j] is true when s[i] == s[j] and the inside, s[i+1..j−1], is a
palindrome too (or is empty or one character). Filling it by length takes O(n²) time and space.
Expanding from centres does the same work with no table. A palindrome is centred on a character (odd length) or on the gap between two (even length), so there are 2n − 1 centres. From each, move two pointers outwards while they stay in the string and point at equal characters; the longest palindrome around that centre lies just inside where they stop.
Keep the best start and length, replacing them only when a palindrome is strictly longer. The centres are visited from left to right, and of two equally long palindromes the one with the earlier centre starts first, so ties keep the earliest.
Time: O(n²) · Space: O(1) beyond the answer