Longest Palindrome in a String

Longest Palindrome in a String

  July 23, 2017    

---

Idea is to use dynamic programming

Set all the [i][j]= true as a single substring is also palindrome

Check for string with length =2 

For len>2 two loops will work and checks whether string at i,j are equal and before that string it was palindrome or not , if so modify

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static String check(String str)
     {
         int len=str.length();
         int index=0;
         int max=1;
         boolean mat[][]=new boolean[len][len];
         for(int i=0;i<len;i++)
         Arrays.fill(mat[i],false);
         for(int i=0;i<len;i++)
         mat[i][i]=true;
         for(int i=0;i<len-1;i++)
         {
             if(str.charAt(i)==str.charAt(i+1))
             {mat[i][i+1]=true;
             if(max<2){
                 max=2;
                 index=i;}
             }
         }
         for(int i=2;i<len;i++)
         {
             for(int j=0;j<len-i;j++)
             {
                 int k=i+j;
                 if(mat[j+1][k-1] && str.charAt(j)==str.charAt(k))
                 {
                     mat[j][k]=true;
                    if(i+1>max){ max=i+1;
                     index=j;}
                 }
             }
         }
        return str.substring(index,index+max);
        // return "index"+index+"max "+max;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   System.out.println(check(ab.next()));
}
}
}