LPS.java

public class Main
{
     private String findLongestPalindromicSubstring(String input)
    {
        //If empty, does not analyze the string
        if(input.isEmpty())
        {
            return "";
        } 

        //holds the length of the string
        int strLen = input.length();
        int longestSoFar = 0, startIndex = 0, endIndex = 0;
        //A 2D array for dynamic programming table
        //the type is boolean because it can only hold the value of 0 or 1
        boolean[][] DPTable = new boolean[strLen][strLen];

        // Looping over the whole string
        for(int j = 0; j < strLen; j++)
        {
            //The main diagonal of the table is always true or 1.
            DPTable[j][j] = true;
            for(int i = 0; i < j; i++)
            {
                //checks the two conditions discussed earlier for
                //palindromic substrings
                if(input.charAt(i) == input.charAt(j) &&
                   (j-i<=2 || DPTable[i+1][j-1]))
                {
                    // If the conditions are met, then we set the cell to true
                    DPTable[i][j] = true;

                    //Compares the length of the current substring to the
                    //the longest substring.
                    if(j-i+1 > longestSoFar)
                    {
                        //If the current substring length is longer, replace 
                        //the corresponding variables with the new values
                        longestSoFar = j-i+1;
                        startIndex = i;
                        endIndex = j;
                    }
                }
            }
        }
        //Returns the longest palindromic substring
        return input.substring(startIndex, endIndex+1);
    }

    public static void main(String[] args)
    {
        //Testing the function
        String input = "aabbab";
        Main test = new Main();
        System.out.println(test.findLongestPalindromicSubstring(input));
    }
}