LongestPaliandromicSubstring.java

package dynamic_programming;

/**
 * Created by gouthamvidyapradhan on 24/02/2017.
 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

 Example:

 Input: "babad"

 Output: "bab"

 Note: "aba" is also a valid answer.
 Example:

 Input: "cbbd"

 Output: "bb"
 */
public class LongestPaliandromicSubstring
{
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception
    {
        System.out.println(new LongestPaliandromicSubstring().longestPalindrome("forgeeksskeegfor"));
    }

    public String longestPalindrome(String s)
    {
        int l = s.length();
        int startIndex = 0; int maxLen = 1;
        boolean[][] A = new boolean[l][l];
        for(int i = 0, j = 0; i < l; i++, j++)
            A[i][j] = true;

        for(int i = 0, j = i + 1; j < l; i++, j++)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                A[i][j] = true;
                startIndex = i;
                maxLen = 2;
            }
        }

        for(int k = 3; k <= l; k++)
        {
            for(int i = 0, j = k - 1; j < l; i++, j++)
            {
                if(s.charAt(i) == s.charAt(j))
                {
                    A[i][j] = A[i + 1][j - 1];
                    if(A[i][j])
                    {
                        if(k > maxLen)
                        {
                            startIndex = i;
                            maxLen = k;
                        }
                    }
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLen);
    }
}