Leet Code : Longest Palindromic Substring Java | CPP | Java Script | Python Solution

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"

Solution :

JavaScript :

var longestPalindrome = function(s) {
    const n = s.length;
    const f = new Array(1001).fill(new Array(1001).fill(false));
    let res = s[0];
    let max = -1;
    
    if(n == 1) {
        return s;
    }
    
    if(n == 2) {
        return s[0] == s[1] ? s : s[0];
    }
    
    for(let i=0; i<n; i++) {
        f[i][i] = true;
    }
    
    for(let i=1; i<n; i++) {
        for(let j=0; j<i; j++) {
            if(s[i] == s[j]) {
                if(i - j == 1) {
                    f[i][j] = true;
                } else {
                    f[i][j] = f[i-1][j+1];
                }
                if(f[i][j] && i-j+1 > max) {
                    max = i-j+1;
                    res = s.substring(j, i+1);
                }
            } else {
                f[i][j] = false;
            }
        }
    }
    
    return res;
};

CPP :

char * longestPalindrome(char * s){
    char dp[1001][1001] = {0};
    unsigned maxlen = 0;
    unsigned startidx = 0;
    
    // Initial setup
    for (int i = 0; i < strlen(s); i++)
        dp[i][i]=1;
    
    for (int i = strlen(s); i >= 0; i--)
    {
        for (int j = strlen(s); j > i; j--)
        {
            unsigned current_len = j-i;
            dp[i][j] = 0; 
            // If the first and the last letter are the same and (the middle is a palindrome OR there is no middle)
            if (s[i] == s[j] && (dp[i+1][j-1] == 1 || (current_len == 1)))
            {
                dp[i][j] = 1;
                if (current_len > maxlen)
                {
                    maxlen = current_len;
                    startidx = i;
                }
            }
        }
    }
    *(s+startidx+maxlen+1) = '\0';
    return (s + startidx);  
}

Python :

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        """edge case and intialization"""
        if not s or len(s) == 1:
            return s 
        LEN = len(s)
        dp = [[False for c in range(LEN)] for r in range(LEN)]
        
        """
        all single characters are palindromes. 
        strings starting at i and ending at i are single characters
        """
        maxlength = 1
        maxsubstring = s[0]
        for i in range(LEN):
            dp[i][i] = True
            
        """
        2 character string -> check if they are palindromes
        start at i and end at i+1
        """
        for i in range(LEN - 1):
            if s[i] == s[i + 1]:
                dp[i][i+1] = True
                maxsubstring = s[i:i+2] #splicing is non-inclusive
                
        """starting at strings of len 3 and up"""
        for l in range(2, LEN):    
            # you can picture processing diagnally strings of length l + 1
            for i in range(LEN - l): 
                #i is the start index, j is the end index.           
                length = l + 1            
                j = i + l
                
                """
                main logic:
                    boundry characters should be equal 
                    and the non-boundry substring should be a palindrome
                """
                if dp[i+1][j-1] and s[i] == s[j]:
                    dp[i][j] = True
                    """
                    in this section of the code
                    the maxlength is bound to be
                    greater than the previous iteration since we 
                    are iterating by string size in the outer most loop
                    """
                    maxlength = length          
                    maxsubstring = s[i:j+1]
                    continue         
        return maxsubstring

About Nilesh Raut

I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.

2 thoughts on “Leet Code : Longest Palindromic Substring Java | CPP | Java Script | Python Solution”

  1. Wonderdul bdat ! I wish to apprenrice hile you amend yor site, how caan i subscribe ffor
    a blo site? The account helped mee a acceptgable deal. I hadd
    besn tiny bbit acquainted oof thi your broadcast offesred bright cllear idea

Leave a Comment

Discover more from NileshBlog.Tech

Subscribe now to keep reading and get access to the full archive.

Continue Reading