medium
Longest Palindromic Substring
Given a string, return the longest contiguous substring that reads the same forwards and backwards.
Constraints
- 1 ≤ s.length ≤ 1000
- Digits and English letters
Examples
in: s = "babad"
out: "bab"
"aba" is also valid.
in: s = "cbbd"
out: "bb"
Recognition clues
- Palindromes are symmetric around a centre
- There are only 2n−1 centres (letters and gaps)
- Grow outward with two pointers while characters match
Pattern
Two PointersWhen order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Solution
For each of the 2n - 1 centres (each character and each gap between characters), expand a left and a right pointer outward while the characters match and the indices stay in bounds. Track the longest span found. Expanding from the centre checks each candidate in time proportional to its length, which bounds the total by O(n^2) with tiny constants.
time O(n^2)space O(1)
Alternative approaches
- A DP table
pal[i][j]costs O(n^2) time and space. Manacher's algorithm computes all palindrome radii in O(n).
Code it yourself
Solve in
Hints: