#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

bool dp[1001][1001];
bool saved[1001][1001];

bool isPalindrome(char *s, int i, int  j){
    if(j<=i) return true;
    if(saved[i][j]) return dp[i][j];
    dp[i][j] = (s[i] == s[j]) && isPalindrome(s, i+1, j-1);
    saved[i][j] = true;
    return dp[i][j];
}

char * longestPalindrome(char * s) {
    
    int ans=0;
    int begin=0;
    int end=0;
    int n = strlen(s);
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++) {
            if(isPalindrome(s, i, j)) {
                if(j-i+1 > ans) {
                    ans = j-i+1;
                    begin = i;
                    end=j+1;
                }
            }
        }
    }
    char *a;
    a = malloc(end-begin+1);
    int j=0;
    for(int i=begin; i<end; i++) 
    a[j++] = s[i];
    a[j]='\0';

    return a;
}