Longest Palindromic Substring LeetCode Solution

Here, We see Longest Palindromic Substring problem Solution. This Leetcode problem done in many programming language like C++, Java, JavaScript, Python etc. with different approach.

Longest Palindromic Substring LeetCode Solution

Longest Palindromic Substring LeetCode Solution

Problem Statement ->

Given a string s, return the longest palindromic substring in s.

A palindrome is a string which reads the same in both directions. For example, S = “aba” is a palindrome, S = “abc” is not.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Longest Palindromic Substring C++ Solution ->

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); } };
Code language: C++ (cpp)

Longest Palindromic Substring Java Solution ->

public class Solution { private int lo, maxLen; public String longestPalindrome(String s) { int len = s.length(); if (len < 2) return s; for (int i = 0; i < len-1; i++) { extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible extendPalindrome(s, i, i+1); //assume even length. } return s.substring(lo, lo + maxLen); } private void extendPalindrome(String s, int j, int k) { while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) { j--; k++; } if (maxLen < k - j - 1) { lo = j + 1; maxLen = k - j - 1; } }}
Code language: Java (java)

Longest Palindromic Substring JavaScript Solution ->

function longestPalindrome(s) { // ll: Left index of the longest palindrome. // rr: Right index of the longest palindrome. let ll = 0, rr = 0; // Iterate all palindromes with center indices // [..., i, ...] or [... i, i+1, ...] for (let i = 0; i < s.length; i++) { for (let j of [i, i+1]) { for (l = i, r = j; s[l] && s[l] === s[r]; l--, r++) // Found a new palindrome [l, ..., i, j, ..., r] // Update the ll, rr if the newly found palindrome is longer than the // existing one. [ll, rr] = (r-l+1) > (rr-ll+1) ? [l, r] : [ll, rr]; } } return s.substring(ll, rr+1); }
Code language: JavaScript (javascript)

Longest Palindromic Substring Python Solution ->

class Solution: def longestPalindrome(self, s: str) -> str: dp = [[False]*len(s) for _ in range(len(s)) ] for i in range(len(s)): dp[i][i]=True ans=s[0] for j in range(len(s)): for i in range(j): if s[i]==s[j] and (dp[i+1][j-1] or j==i+1): dp[i][j]=True if j-i+1>len(ans): ans=s[i:j+1] return ans
Code language: Python (python)

Leave a Comment

Your email address will not be published. Required fields are marked *