class Solution {
    int[][] arr;
    String result = "";
    public String longestPalindrome(String s) {
        arr = new int[s.length()+1][s.length()+1];
        
        for(int i=0; i<s.length(); i++) {
            longestPalindromeAux(s, i, i+1);
        }
        return result;
    }
    
    public int longestPalindromeAux(String s, int from, int to) {
        if(to > s.length()) {
            return -1;
        }
        
        if(from < 0) {
            return -1;
        }
        
        if(arr[from][to] != 0) {
            return arr[from][to];
        }
        
        String thisString = s.substring(from, to);
        if(!isPalindrome(thisString)) {            
            return -1;
        }
        
        if(result.length() < thisString.length())
            result = thisString;
        
        int r1 = longestPalindromeAux(s, from, to+1);
        
        int r2 = longestPalindromeAux(s, from-1, to);
        
        int r3 = longestPalindromeAux(s, from-1, to+1);
        
        arr[from][to] = Math.max(r1, Math.max(r2, r3));
        return arr[from][to];
    }
    
    // Map<String, Boolean> map = new HashMap<>();
    boolean isPalindrome(String s) {
        // if(map.containsKey(s))
        //     return map.get(s);
        int l = 0;
        int r = s.length()-1;
        while(l < r) {
            if(s.charAt(l)  != s.charAt(r)) {
                // map.put(s, false);
                return false;
            }
            l = l+1;
            r = r-1;
        }
        // map.put(s, true);
        return true;
    }
}