class Solution {
    public String longestPalindrome(String s) {
        String s2 = new StringBuilder(s).reverse().toString();

        int n = s.length();
        int m = s2.length();

        // create a matrix
        int[][] t = new int[n+1][m+1];

        // intialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

        // find LCS
        int maxLength = 0;
        int endIndex = 0;
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(s.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                    int currentLength = t[i][j];

                    // start index in original string
                    // If a substring of length len ends at i-1 in s, its start index in s is:
                    int startIndex = i - currentLength;
                    // In the reversed string, the corresponding start should be: (n-j)
                    int mirroredIndex = n - j;

                    // check alignment
                    if(startIndex == mirroredIndex)
                    {
                        if(currentLength > maxLength)
                        {
                            maxLength = currentLength;
                            endIndex = i-1;
                        }
                    }
                }
            }
        }
        return s.substring(endIndex - maxLength + 1, endIndex + 1);
    }
}