LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION | LEETCODE PROGRAM SOLUTION
We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:
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.
Approach 1: Naive
- Time: O(n^2)O(n2)
- Space: O(n)O(n)
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN 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};
}
};
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN 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};
}
}
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN PYTHON
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]
Approach 2: Manacher
- Time: O(n)O(n)
- Space: O(n)O(n)
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN 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;
}
};
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN 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();
}
}
LONGEST PALINDROMIC SUBSTRING PROGRAM SOLUTION IN 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]
