LeetCode 5: Longest Palindromic Substring (Center Expansion)
LeetCode 5StringTwo PointersToday we solve LeetCode 5 - Longest Palindromic Substring.
Source: https://leetcode.com/problems/longest-palindromic-substring/
English
Problem Summary
Given a string s, return the longest palindromic substring in s. A palindrome reads the same forward and backward.
Key Insight
Every palindrome has a center. For each index, expand around two centers: odd-length center (i, i) and even-length center (i, i+1). Keep the longest range found.
Brute Force and Why Insufficient
Brute force checks all substrings and verifies palindrome each time. This is O(n^3) in worst case, too slow for larger inputs.
Optimal Algorithm (Step-by-Step)
1) Initialize best start index and best length.
2) For each index i, expand around (i, i) and (i, i+1) while characters match.
3) Each expansion returns palindrome boundaries; update best if longer.
4) Return s.substring(bestStart, bestStart + bestLen).
Complexity Analysis
Time: O(n^2) in worst case (e.g., all same chars).
Space: O(1) extra space.
Common Pitfalls
- Forgetting even-length centers.
- Off-by-one when converting inclusive boundaries to substring ranges.
- Updating best length before expansion stops, causing wrong range.
- Returning indices instead of actual substring.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i); // odd
int len2 = expand(s, i, i + 1); // even
int len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}func longestPalindrome(s string) string {
n := len(s)
if n <= 1 {
return s
}
start, maxLen := 0, 1
expand := func(l, r int) int {
for l >= 0 && r < n && s[l] == s[r] {
l--
r++
}
return r - l - 1
}
for i := 0; i < n; i++ {
len1 := expand(i, i)
len2 := expand(i, i+1)
length := len1
if len2 > length {
length = len2
}
if length > maxLen {
maxLen = length
start = i - (length-1)/2
}
}
return s[start : start+maxLen]
}class Solution {
public:
string longestPalindrome(string s) {
int n = (int)s.size();
if (n <= 1) return s;
int start = 0, maxLen = 1;
auto expand = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
}
return r - l - 1;
};
for (int i = 0; i < n; ++i) {
int len1 = expand(i, i);
int len2 = expand(i, i + 1);
int len = max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substr(start, maxLen);
}
};class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
start, max_len = 0, 1
def expand(l: int, r: int) -> int:
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1
for i in range(len(s)):
len1 = expand(i, i)
len2 = expand(i, i + 1)
cur = max(len1, len2)
if cur > max_len:
max_len = cur
start = i - (cur - 1) // 2
return s[start:start + max_len]var longestPalindrome = function(s) {
if (s.length <= 1) return s;
let start = 0;
let maxLen = 1;
const expand = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
return r - l - 1;
};
for (let i = 0; i < s.length; i++) {
const len1 = expand(i, i);
const len2 = expand(i, i + 1);
const len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - Math.floor((len - 1) / 2);
}
}
return s.substring(start, start + maxLen);
};中文
题目概述
给定字符串 s，返回其中最长的回文子串。回文串正着读和反着读相同。
核心思路
回文一定有“中心”。对每个位置做两次扩展：奇数中心 (i,i) 和偶数中心 (i,i+1)，持续向两边匹配，记录最长区间。
暴力解法与不足
暴力法枚举所有子串并逐个判断是否回文，最坏时间复杂度 O(n^3)，规模稍大就会超时。
最优算法（步骤）
1）维护最佳起点与长度。
2）遍历每个下标 i，分别从 (i,i) 与 (i,i+1) 扩展。
3）扩展结束后得到当前最大回文长度，若更长则更新答案。
4）最后截取并返回最长回文子串。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(1)。
常见陷阱
- 忘记处理偶数长度回文中心。
- 下标与 substring 边界换算时 off-by-one。
- 在扩展未结束时就更新边界导致答案错位。
- 返回了下标而不是子串本身。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i);
int len2 = expand(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}func longestPalindrome(s string) string {
n := len(s)
if n <= 1 {
return s
}
start, maxLen := 0, 1
expand := func(l, r int) int {
for l >= 0 && r < n && s[l] == s[r] {
l--
r++
}
return r - l - 1
}
for i := 0; i < n; i++ {
len1 := expand(i, i)
len2 := expand(i, i+1)
length := len1
if len2 > length {
length = len2
}
if length > maxLen {
maxLen = length
start = i - (length-1)/2
}
}
return s[start : start+maxLen]
}class Solution {
public:
string longestPalindrome(string s) {
int n = (int)s.size();
if (n <= 1) return s;
int start = 0, maxLen = 1;
auto expand = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
}
return r - l - 1;
};
for (int i = 0; i < n; ++i) {
int len1 = expand(i, i);
int len2 = expand(i, i + 1);
int len = max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substr(start, maxLen);
}
};class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
start, max_len = 0, 1
def expand(l: int, r: int) -> int:
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1
for i in range(len(s)):
len1 = expand(i, i)
len2 = expand(i, i + 1)
cur = max(len1, len2)
if cur > max_len:
max_len = cur
start = i - (cur - 1) // 2
return s[start:start + max_len]var longestPalindrome = function(s) {
if (s.length <= 1) return s;
let start = 0;
let maxLen = 1;
const expand = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
return r - l - 1;
};
for (let i = 0; i < s.length; i++) {
const len1 = expand(i, i);
const len2 = expand(i, i + 1);
const len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - Math.floor((len - 1) / 2);
}
}
return s.substring(start, start + maxLen);
};
Comments