Given a string s, return its longest substring that reads the same forwards and backwards (a palindrome). If several palindromes share the maximum length, any one of them is accepted.
Example 1
Input: s = "babad"
Output: "bab"
"aba" is also a valid answer.Example 2
Input: s = "cbbd"
Output: "bb"
Constraints
- 1 <= s.length <= 1000
- `s` contains only digits and English letters
Hints
Frequently asked at: Amazon, Microsoft, Google, Adobe, Samsung
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking all O(n^2) substrings, each in O(n), gives O(n^3). A palindrome mirrors around its centre, so instead of guessing the ends, pick the centre and grow outwards while the characters on both sides match. Odd palindromes centre on a character and even ones on the gap between two characters, so there are 2n - 1 centres. Each expansion is O(n), for O(n^2) overall with O(1) extra space.
Algorithm
- Keep
startandbestLenfor the best palindrome found. - For each index
i, expand from(i, i)and from(i, i + 1). - Expanding: while
l >= 0,r < nands[l] == s[r], dol--,r++. The palindrome iss[l+1 .. r-1]of lengthr - l - 1. - If that length beats
bestLen, updatestartandbestLen. - Return
s[start : start + bestLen].
Time:
O(n^2)Space: O(1)Interview tip: Forgetting even-length centres (like
"bb") is the most common bug. If asked for better than O(n^2), mention Manacher's algorithm, which runs in O(n); the DP table is another O(n^2) option but uses O(n^2) memory.class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) start, best_len = 0, 0Β def expand(l, r): while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 return l + 1, r - l - 1 # start and length of s[l+1 .. r-1]Β for i in range(n): for l, r in ((i, i), (i, i + 1)): # odd and even centres st, length = expand(l, r) if length > best_len: start, best_len = st, length return s[start:start + best_len]Ctrl + Enter runs the examples