In this post, we are going to solve the Longest Palindromic Substring Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
Problem
Given a string s, return the longest palindromic substring in s.
A string is called a palindrome string if the reverse of that string is the same as the original string.
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 <= 1000s consist of only digits and English letters.
Now, let’s see the code of Longest Palindromic Substring Leetcode Solution.
Longest Palindromic Substring Leetcode Solution in Python
class Solution:
def longestPalindrome(self, s: str) -> str:
p = ''
for i in range(len(s)):
p1 = self.get_palindrome(s, i, i+1)
p2 = self.get_palindrome(s, i, i)
p = max([p, p1, p2], key=lambda x: len(x))
return p
def get_palindrome(self, s: str, l: int, r: int) -> str:
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l+1:r]Longest Palindromic Substring Leetcode Solution in CPP
class Solution {
public:
string longestPalindrome(string s)
{
int len = s.size();
int dp[len][len];
memset(dp,0,sizeof(dp));
int end=1;
int start=0;
for(int i=0;i<len;i++)
{
dp[i][i] = 1;
}
for(int i=0;i<len-1;i++)
{
if(s[i]==s[i+1])
{ dp[i][i+1]=1;start=i;end=2;}
}
for(int j=2;j<len;j++)
{
for(int i=0;i< len-j;i++)
{
int left=i; //start point
int right = i+j; //ending point
if(dp[left+1][right-1]==1 && s[left]==s[right])
{
dp[left][right]=1; start=i; end=j+1;
}
}
}
return s.substr(start, end);
}
};Longest Palindromic Substring Leetcode Solution in Java
class Solution {
public String longestPalindrome(String s) {
int n = s.length(), start = 0, end = 0;
boolean[][] dp = new boolean[n][n];
for (int len=0; len<n; len++) {
for (int i=0; i+len<n; i++) {
dp[i][i+len] = s.charAt(i) == s.charAt(i+len)
&& (len < 2 || dp[i+1][i+len-1]);
if (dp[i][i+len] && len > end - start) {
start = i;
end = i + len;
}
}
}
return s.substring(start, end + 1);
}
}Note: This problem Longest Palindromic Substring is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
