Header Ads Widget

Longest Palindromic Substring | Leetcode solution

Given a string s, return the longest 

 

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.

 Code(C++):-

class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
int dp[n][n];
memset(dp,0,n*n*sizeof(int));
for(int i=0;i<n;i++)
dp[i][i]=1;
int maxlength=1;
int starting =0;
for(int i=0;i<n-1;i++)
{
if(s[i]==s[i+1])
{
starting=i;
dp[i][i+1]=1;
maxlength=2;
}
}
// for substring greater than 2
for(int k=3;k<=n;k++)
{
for(int i=0;i<=n-k;i++)
{
int j=i+k-1;
if(dp[i+1][j-1] and s[i]==s[j])
{
if(k>maxlength)
{
maxlength=k;
starting=i;
}
dp[i][j]=1;
}
}
}
string ans="";
for(int i=starting;i<starting+maxlength;i++)
{
ans+=(s[i]);
}
return ans;
}
};

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-