Longest Palindromic Substring

1. Example
         
Not DP           s        s
         15 16 17 18
         isPalindrome(s, 16,16), right = left         sine  i =16 %2 == 0

         isPalindrome(s, 17,18),  right = left +1 since i=17 %2 =1

DP
01234567 89
forgee  ks s k e e g f o r
i iiiiiiiiii i=7 i  i  i i  i  i i i
              j       => iter1  , s[i]= s[j] and j-i = 0 <= 1
              i
                 j     => iter2,   s[i] = s[j] and j-i=1 <= 1, palin[7][8] = true
              i
                   j  => iter3, s[i] != s[j]
            i=6
            j
            i
               j
            i
                 j
            i
                    j=>s[i]=s[j] and palin[7][8] = ture => palin[6][9] = true, len = 9-6+1 = 4, substring(6,10)

s= "forgeeksskeegfor"

Longest palindrome substring is: geeksskeeg

2. Implementation
Q1: for i=0
          for  j=i+1
           curr = s.substring(i,j)
            if (   curr.length() > maxLen  )
            maxLen =curr.length() ;
            str = curr;
A1: Time : O(n^2*n isPalindrome), Space:O(1)
Q1:           ss
                kssk
              eksske
            eeksskee
          geeksskeeg
A1: Time:O(n^2), Space:O(n^2)
s[i] = s[j] and res[]
       s[0] res[0]
       s[0] = s[1]


Q1:     a     b      c       c      b        a         d
        0 1 2  3  4  5  6  7  8  9  10 11 12  13
A1: Time: O( 2n-1 gap* n isPalindrome), Space:O(1)

// Center outward
// Time:O(n^2), Space:O(1)
public String longestPalindrome(String s)
{


    
    String res = new String();
    if ( s == null || s.length()== 0)
       return res;



    //  n + n-1  = 2n-1
    for (int  i= 0 ; i < 2*s.length() -1;i++)
    {




         int left = i/2; 
         int right = i/2;
         if ( i%2 == 1 )
             right++;
          


          
         int maxLen = 0;
         String str = lengthOfPalindrome(String s, int left, int right);
         if ( str.length() > maxLen)
         { 
            maxLen = str.length();
            res = str;
         } 


         
    }



    return res;



}


private String lengthOfPalindrome( String s , int left ,int right )
{




    int l = left;
    int r = right;
    //  <-l data-blogger-escaped-r-="">
    while ( l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r) )
    {
           l--;
           r++;
    }





    return s.subString(l+1, r); // l become l-- but it is now l and r become r++ and it's right fit for substring()




}

// Dynamic Programming
// Time:O(n^2), Space:O(n^2)
public String longestPalindrome( String s )
{
    





      String res = new String();
      // validate the input
      if (s== null || s.length() == 0)





      boolean[][] palin = new Boolean[][];
      int maxLen = 0;
      String res = "";
      for (int i = s.length()-1; i>=0 ; i--)
      {
           for (int j = i; j < s.length();j++)
           {
               



               if ( s.charAt(i) == s.charAt(j) &&     
                    (j-i <=1 || palin[i+1][j-1] == true )   )
               {
                    palin[i][j] = true;
                    if ( maxLen < j-i+1)
                    {
                          maxLen = j-i+1;
                          res = s.subStirng(i, j+1);                    
                    }
               }






           }
      }



   
      return res;



}

// REturn length of the longest palindrome string
public int lps_recursive(Stirng s)
{


     return lps(s,0,s.length()-1);


}
private int lps(String s, int left, int right)
{



    if (left > right )
       return 0;
    if (left == right )   
       return 1;



    if ( s.charAt(left) == s.charAt(right))
       return lps(s, left+1, right-1) + 2 ;
    else 
       return Math.max( lps(s,left+1,right), lps(s, left, right-1)  );



}

3. Similar Ones
(H) Shortest Palindrome
(E) Palindrome Permutation
(H)  Longest Valid Parentheses
(M) Longest Common Prefix
(M) Longest Substring Without Repeating Characters
(H) Longest Consecutive Sequece