Problem
Given a string s, return the longest palindromic substring in s.
Example
Input: "babad"
Output: "bab" or "aba"Solution
Expand around center. Try every position as a potential palindrome center (both odd and even length).
def longest_palindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]
longest = ''
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
for p in (odd, even):
if len(p) > len(longest):
longest = p
return longestfunction longestPalindrome(s) {
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
return s.slice(l + 1, r);
}
let longest = '';
for (let i = 0; i < s.length; i++) {
const odd = expand(i, i);
const even = expand(i, i + 1);
if (odd.length > longest.length) longest = odd;
if (even.length > longest.length) longest = even;
}
return longest;
}string longestPalindrome(string s) {
auto expand = [&](int l, int r) {
while (l >= 0 && r < s.size() && s[l] == s[r]) { l--; r++; }
return s.substr(l + 1, r - l - 1);
};
string longest = "";
for (int i = 0; i < s.size(); i++) {
string odd = expand(i, i);
string even = expand(i, i + 1);
if (odd.size() > longest.size()) longest = odd;
if (even.size() > longest.size()) longest = even;
}
return longest;
}public String longestPalindrome(String s) {
String longest = "";
for (int i = 0; i < s.length(); i++) {
String odd = expand(s, i, i);
String even = expand(s, i, i + 1);
if (odd.length() > longest.length()) longest = odd;
if (even.length() > longest.length()) longest = even;
}
return longest;
}
private String expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return s.substring(l + 1, r);
}Complexity
- Time: O(n²)
- Space: O(1)
Explanation
Every palindrome has a center (single char for odd, gap between two chars for even). Try each center and expand outward as long as characters match.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?