5. Longest Palindromic Substring

Given a string `s`, return the longest palindromic substring in `s`.

Example 1:

``````**Input:** s = "babad"
**Output:** "bab"
**Explanation:** "aba" is also a valid answer.
``````

Example 2:

``````**Input:** s = "cbbd"
**Output:** "bb"
``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consist of only digits and English letters.

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n - 1; ++i) {
searchPalindrome(s, i, i, start, maxLen);
searchPalindrome(s, i, i + 1, start, maxLen);
}
return s.substr(start, maxLen);
}
void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left; ++right;
}
if (maxLen < right - left - 1) {
start = left + 1;
maxLen = right - left - 1;
}
}
};
``````

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n;) {
if (n - i <= maxLen / 2) break;
int left = i, right = i;
while (right < n - 1 && s[right + 1] == s[right]) ++right;
i = right + 1;
while (right < n - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right; --left;
}
if (maxLen < right - left + 1) {
maxLen = right - left + 1;
start = left;
}
}
return s.substr(start, maxLen);
}
};
``````

dp[i, j] = true if i == j

= s[i] == s[j] if j = i + 1

= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1

``````class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int n = s.size(), left = 0, len = 1;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
for (int j = 0; j < i; ++j) {
dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
if (dp[j][i] && len < i - j + 1) {
len = i - j + 1;
left = j;
}
}
}
return s.substr(left, len);
}
};
``````

``````class Solution {
public:
string longestPalindrome(string s) {
string t ="\$#";
for (int i = 0; i < s.size(); ++i) {
t += s[i];
t += '#';
}
vector<int> p(t.size());
int id = 0, mx = 0, resId = 0, resMx = 0;
for (int i = 1; i < t.size(); ++i) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resMx < p[i]) {
resMx = p[i];
resId = i;
}
}
return s.substr((resId - resMx) / 2, resMx - 1);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/5

Shortest Palindrome

Palindrome Permutation

Palindrome Pairs

Longest Palindromic Subsequence

Palindromic Substrings

https://leetcode.com/problems/longest-palindromic-substring/

https://leetcode.com/problems/longest-palindromic-substring/discuss/2928/Very-simple-clean-java-solution

https://leetcode.com/problems/longest-palindromic-substring/discuss/2923/Simple-C%2B%2B-solution-(8ms-13-lines)

https://leetcode.com/problems/longest-palindromic-substring/discuss/2921/Share-my-Java-solution-using-dynamic-programming

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation