Codekata Palindromic Problem

Given a string of length N, find the longest palindromic substring.
Input Size : 1 <= N <= 1000

Sample Testcase :
INPUT
DIEHEIDI
OUTPUT
DIEHEID