In this guide we will provide 5. Longest Palindromic Substring LeetCode Solution with best time and space complexity. The solution to Longest Palindromic Substring problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Problem Statement of 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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
5. Longest Palindromic Substring LeetCode 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:
// Returns the (start, end) indices of the longest palindrome extended from
// the substring 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};
}
}; /* code provided by PROGIEZ */
5. Longest Palindromic Substring LeetCode 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);
}
// Returns the (start, end) indices of the longest palindrome extended from
// the substring 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};
}
} // code provided by PROGIEZ
5. Longest Palindromic Substring LeetCode Solution in Python
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ''
# (start, end) indices of the longest palindrome in s
indices = [0, 0]
def extend(s: str, i: int, j: int) -> tuple[int, int]:
"""
Returns the (start, end) indices of the longest palindrome extended from
the substring s[i..j].
"""
while i >= 0 and j < len(s):
if s[i] != s[j]:
break
i -= 1
j += 1
return i + 1, j - 1
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] #code by PROGIEZ
