In this post, you will know how 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.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
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 <= 1000sconsist of only digits and English letters.
Longest Palindromic Substring Leetcode Solutions 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 Solutions 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 Solutions 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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
NEXT: Reverse Integer Leetcode Solution
