DSA problem
Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s. If there are multiple such substrings of equal maximum length, you may return any one.
A palindrome reads the same forward and backward. A substring is a contiguous slice — unlike a subsequence, you cannot skip characters in the middle.
The brute force checks each of O(n^2) substrings for palindromicity in O(n), costing O(n^3). The standard O(n^2) approaches mirror the techniques for counting palindromic substrings:
Expand Around Center. Every palindrome has a center, so iterate over the 2n - 1 possible centers (each character for odd length, each adjacent pair for even length) and expand outward while characters match. Track the best length and starting index seen so far. This solves the problem in O(n^2) time and O(1) extra space — the recommended production-grade solution.
2D DP. Define dp[i][j] as a boolean for "s[i..j] is a palindrome", filled by increasing length. The DP is conceptually clean but uses O(n^2) space.
Manacher's algorithm achieves O(n) but is rarely required at the typical constraint range of n <= 1000.
Examples
s = "babad""bab"s = "cbbd""bb"s = "a""a"Constraints
- 1 <= s.length <= 1000
- s consist of only digits and English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.