LeetCode (Longest Pallidromic Substring)(TLE!)

general
,
1

Can anyone please help me with optimising the solution

code-
checker() is used to generate all the substring possible
map<pair,int> is used to store if (string of i+1,j-1 is. a pallindrome or not)
@ssrivastava990 ,@galencolin, @akshitm16, @ssjgz, @dardev

class Solution {

public:
string ans;
int mx=0,x=0,y=0,n;
int dp[1001][1001];

map<pair<int,int>,int>mp;

void checker(string s,int i,int j)
{
    if(i>j || j<0 || i<0 || i>n || j>n)
    {
        return;
    }
  
    if(dp[i][j]!=-1)return;
    dp[i][j]=0;
 if(dp[i+1][j]==-1) checker(s,i+1,j);
if(j>0) if(dp[i][j-1]==-1) checker(s,i,j-1);
    if((s[i]==s[j]&& ((mp[{i+1,j-1}]==1)||(j-i<=1))))
        {
        if((j-i)>mx){
            mx = j-i;
            x=i;y=j;
        }
            mp[{i,j}]=1;
        }
    
}
  

string longestPalindrome(string s) {
    if(s.size()==0)return s;
    n = s.size();
    memset(dp,-1,sizeof(dp));  
    for(int i=0;i<n;i++)
    {
        mp[{i,i}]=1;
    }
   
    checker(s,0,s.size()-1);
    for(int k=x;k<=y;k++)
        ans+=s[k];
    return ans;
}

};

2

your solution is not visible

1 Like
3

@lazarus123 the solution isn’t available…

1 Like
4

I program in Java and this is my solution. Please have a look

  class Solution 
    {
        public String longestPalindrome(String s) 
        {
            if(s==null || s.length()==0)
            {
                return "";
            }
            int len=s.length();
            boolean dp[][]=new boolean[len][len];
            for(int i=0;i<len;i++) // substring of length 1  // example abc where a would be the answer
            {
                dp[i][i]=true;
            }
            
            int maxlen=1;
            int start=0;
            for(int i=0;i<len-1;i++) //substring of length 2 // abbd where bb would the answer
            {
                if(s.charAt(i)==s.charAt(i+1))
                {
                    dp[i][i+1]=true;
                    maxlen=2;
                    start=i;
                    
                }
            }
            int k;
            
            for(k=3;k<=len;k++) // for the substrings with length greater than or equal to 3.
            {
                for(int i=0;i<len-k+1;i++)
                {
                    int j=i+k-1;
                    if(  s.charAt(i)==s.charAt(j) && dp[i+1][j-1]==true)
                    {
                        dp[i][j]=true;
                        if(k>maxlen)
                        {
                            maxlen=k;
                            start=i;
                        }
                    }
                }
            }
            return s.substring(start,start+maxlen);
        }
}
5

Check this out: undefined - undefined - LeetCode

7

I am not able to relate it !! I am using map to check for (i,j)-> if(i+1,j-1) is valid string