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 <= 1000sconsist of only digits and English letters.
Solutions
1. Naive Approach
✅Time: O(n*n)
✅Space: O(n)
C++
class Solution {
public:
string longestPalindrome(string s) {
if (s.empty())
return "";
// [start, end] indices of the longest palindrome in s
pair<int, int> indices{0, 0};
for (int i = 0; i < s.length(); ++i) {
const auto& [l1, r1] = extend(s, i, i);
if (r1 - l1 > indices.second - indices.first)
indices = {l1, r1};
if (i + 1 < s.length() && s[i] == s[i + 1]) {
const auto& [l2, r2] = extend(s, i, i + 1);
if (r2 - l2 > indices.second - indices.first)
indices = {l2, r2};
}
}
return s.substr(indices.first, indices.second - indices.first + 1);
}
private:
// return [start, end] indices of the longest palindrome extended from s[i..j]
pair<int, int> extend(const string& s, int i, int j) {
for (; i >= 0 && j < s.length(); --i, ++j)
if (s[i] != s[j])
break;
return {i + 1, j - 1};
}
};
Java
class Solution {
public String longestPalindrome(String s) {
if (s.isEmpty())
return "";
// [start, end] indices of the longest palindrome in s
int[] indices = {0, 0};
for (int i = 0; i < s.length(); ++i) {
int[] indices1 = extend(s, i, i);
if (indices1[1] - indices1[0] > indices[1] - indices[0])
indices = indices1;
if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
int[] indices2 = extend(s, i, i + 1);
if (indices2[1] - indices2[0] > indices[1] - indices[0])
indices = indices2;
}
}
return s.substring(indices[0], indices[1] + 1);
}
// return [start, end] indices of the longest palindrome extended from s[i..j]
private int[] extend(final String s, int i, int j) {
for (; i >= 0 && j < s.length(); --i, ++j)
if (s.charAt(i) != s.charAt(j))
break;
return new int[] {i + 1, j - 1};
}
}
Python
class Solution:
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ''
def extend(s: str, i: int, j: int) -> Tuple[int, int]:
while i >= 0 and j < len(s):
if s[i] != s[j]:
break
i -= 1
j += 1
return i + 1, j - 1
indices = [0, 0]
for i in range(len(s)):
l1, r1 = extend(s, i, i)
if r1 - l1 > indices[1] - indices[0]:
indices = l1, r1
if i + 1 < len(s) and s[i] == s[i + 1]:
l2, r2 = extend(s, i, i + 1)
if r2 - l2 > indices[1] - indices[0]:
indices = l2, r2
return s[indices[0]:indices[1] + 1]
2. Manacher Approach
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
string longestPalindrome(string s) {
// @ and $ signs are sentinels appended to each end to avoid bounds checking
const string& t = join('@' + s + '$', '#');
const int n = t.length();
// t[i - maxExtends[i]..i) ==
// t[i + 1..i + maxExtends[i]]
vector<int> maxExtends(n);
int center = 0;
for (int i = 1; i < n - 1; ++i) {
const int rightBoundary = center + maxExtends[center];
const int mirrorIndex = center - (i - center);
maxExtends[i] =
rightBoundary > i && min(rightBoundary - i, maxExtends[mirrorIndex]);
// Attempt to expand palindrome centered at i
while (t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]])
++maxExtends[i];
// If palindrome centered at i expand past rightBoundary,
// adjust center based on expanded palindrome.
if (i + maxExtends[i] > rightBoundary)
center = i;
}
// Find the maxExtend and bestCenter
int maxExtend = 0;
int bestCenter = -1;
for (int i = 0; i < n; ++i)
if (maxExtends[i] > maxExtend) {
maxExtend = maxExtends[i];
bestCenter = i;
}
const int l = (bestCenter - maxExtend) / 2;
const int r = (bestCenter + maxExtend) / 2;
return s.substr(l, r - l);
}
private:
string join(const string& s, char c) {
string joined;
for (int i = 0; i < s.length(); ++i) {
joined += s[i];
if (i != s.length() - 1)
joined += c;
}
return joined;
}
};
Java
class Solution {
public String longestPalindrome(String s) {
final String t = join('@' + s + '$', '#');
final int n = t.length();
// t[i - maxExtends[i]..i) ==
// t[i + 1..i + maxExtends[i]]
int[] maxExtends = new int[n];
int center = 0;
for (int i = 1; i < n - 1; ++i) {
final int rightBoundary = center + maxExtends[center];
final int mirrorIndex = center - (i - center);
maxExtends[i] =
rightBoundary > i && Math.min(rightBoundary - i, maxExtends[mirrorIndex]) > 0 ? 1 : 0;
// Attempt to expand palindrome centered at i
while (t.charAt(i + 1 + maxExtends[i]) == t.charAt(i - 1 - maxExtends[i]))
++maxExtends[i];
// If palindrome centered at i expand past rightBoundary,
// adjust center based on expanded palindrome.
if (i + maxExtends[i] > rightBoundary)
center = i;
}
// Find the maxExtend and bestCenter
int maxExtend = 0;
int bestCenter = -1;
for (int i = 0; i < n; ++i)
if (maxExtends[i] > maxExtend) {
maxExtend = maxExtends[i];
bestCenter = i;
}
return s.substring((bestCenter - maxExtend) / 2, (bestCenter + maxExtend) / 2);
}
private String join(final String s, char c) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
sb.append(s.charAt(i));
if (i != s.length() - 1)
sb.append(c);
}
return sb.toString();
}
}
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
# @ and $ signs are sentinels appended to each end to avoid bounds checking
t = '#'.join('@' + s + '$')
n = len(t)
# t[i - maxExtends[i]..i) ==
# t[i + 1..i + maxExtends[i]]
maxExtends = [0] * n
center = 0
for i in range(1, n - 1):
rightBoundary = center + maxExtends[center]
mirrorIndex = center - (i - center)
maxExtends[i] = rightBoundary > i and \
min(rightBoundary - i, maxExtends[mirrorIndex])
# Attempt to expand palindrome centered at i
while t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]]:
maxExtends[i] += 1
# If palindrome centered at i expand past rightBoundary,
# adjust center based on expanded palindrome.
if i + maxExtends[i] > rightBoundary:
center = i
# Find the maxExtend and bestCenter
maxExtend, bestCenter = max((extend, i)
for i, extend in enumerate(maxExtends))
return s[(bestCenter - maxExtend) // 2:(bestCenter + maxExtend) // 2]
Watch Tutorial
Checkout more Solutions here
