In this post, we are going to solve the 5. Longest Palindromic Substring problem of Leetcode. This problem 5. Longest Palindromic Substring is a Leetcode medium level problem. Let’s see code, 5. Longest Palindromic Substring.

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 <= 1000
• s consist of only digits and English letters.

Now, let’s see the code of 5. Longest Palindromic Substring – Leetcode Solution.

Longest Palindromic Substring – Leetcode Solution

5. Longest Palindromic Substring – 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);
    }   
}

5. Longest Palindromic Substring – Solution in C++

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);
}
};

5. Longest Palindromic Substring – 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]

Note: This problem 5. Longest Palindromic Substring is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.