As we all know, a palindrome is a word that equals its reverse. Here are some examples of palindromes: malayalam, gag, appa, amma.
We consider any sequence consisting of the letters of the English alphabet to be a word. So axxb,abbba and bbbccddx are words for our purpose. And aaabbaaa, abbba and bbb are examples of palindromes.
By a subword of a word, we mean a contiguous subsequence of the word. For example the subwords of the word abbba are a, b, ab, bb, ba, abb, bbb, bba, abbb, bbba and abbba.
In this task you will given a word and you must find the longest subword of this word that is also a palindrome.
For example if the given word is abbba then the answer is abbba. If the given word is abcbcabbacba then the answer is bcabbacb.

-----Input:-----
The first line of the input contains a single integer $N$ indicating the length of the word. The following line contains a single word of length $N$, made up of the letters a,b,…, z.

-----Output:-----
The first line of the output must contain a single integer indicating the length of the longest subword of the given word that is a palindrome. The second line must contain a subword that is a palindrome and which of maximum length. If there is more than one subword palindrome of maximum length, it suffices to print out any one.

-----Constraints:-----
- $1 \leq N \leq 5000$. 
- You may assume that in $30 \%$ of the inputs $1 \leq N \leq 300$.

-----Sample Input 1:-----
5
abbba

-----Sample Output 1:-----
5
abbba

-----Sample Input 2:-----
12
abcbcabbacba

-----Sample Output 2:-----
8
bcabbacb

Difficulty: interview

Starter code:

Solutions:
########################################################
################# Template #############################
import sys
import math
def Int(): return int(input())
def Str(): return input()
def Ints(): return list(map(int,input().split(" ")))
def int_arr(): return list(map(int,input().strip().split(" ")))
def str_arr(): return list(map(str,input().split(" ")))
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
#########################################################
#vsInput()
def strings(s):
    n=len(s)
    count=0
    for i in range(n//2):
        if s[i]!=s[n-1-i]:
            count=1
            break
    return count==0
    
n=int(input())
s=input()
palindrome = ""
for i in range(n-1):
    for j in range(i+1,n+1):
        nextstring = s[i:j]
        if strings(nextstring) and len(nextstring)>len(palindrome):
            palindrome=nextstring
print(len(palindrome))
print(palindrome)


import sys
from sys import maxsize
def inputint(): return list(map(int, sys.stdin.readline().strip().split()))
def inputlist(): return list(map(int, sys.stdin.readline().strip().split()))
def inputstr(): return list(sys.stdin.readline().strip().split())
def check(s,i,j):
    while i>=0 and j<len(s):
        if s[i]==s[j]:
            i-=1
            j+=1
        else:
            break
    i+=1
    j-=1
    #print(s[i:j+1])
    return j-i+1
def solve():
    n=int(sys.stdin.readline())
    s=sys.stdin.readline()
    c=0
    start,end=0,0
    for i in range(0,n):
        t1=check(s,i,i)
        t2=check(s,i,i+1)
        c=max(t1,t2)
        #print(c)
        if c>end-start:
            start=i-((c-1)//2)
            end=i+(c//2)
    print(end-start+1)
    print(s[start:end+1])
    
solve()


def check(s,i,j):
    while i>=0 and j<len(s):
        if s[i]==s[j]:
            i-=1
            j+=1
        else:
            break
    i+=1
    j-=1
    #print(s[i:j+1])
    return j-i+1
def solve():
    n=int(input())
    s=input()
    c=0
    start,end=0,0
    for i in range(0,n):
        t1=check(s,i,i)
        t2=check(s,i,i+1)
        c=max(t1,t2)
        #print(c)
        if c>end-start:
            start=i-((c-1)//2)
            end=i+(c//2)
    print(end-start+1)
    print(s[start:end+1])
    
solve()


def get_longest_palindromes(strng):
    N = len(strng)
    cache = [[None] * N for _ in range(N)]

    def is_palindrome(lo, hi):
        if cache[lo][hi] is not None:
            return cache[lo][hi]

        if lo == hi:
            return True
        elif lo + 1 == hi:
            return strng[lo] == strng[hi]

        ans = False if strng[lo] != strng[hi] else is_palindrome(lo+1, hi-1)
        cache[lo][hi] = ans
        return ans

    def generate_palindromes():
        ret = []
        longest = N
        found = False

        if not strng:
            return ['']

        for l in range(N, 0, -1):
            found = False
            for s in range(N-l+1):
                if is_palindrome(s, s+l-1):
                    found = True
                    ret.append(strng[s:s+l])
            if found:
                break
        return ret

    return generate_palindromes()
try:
    n = int(input())
    string = input()
    print(len(get_longest_palindromes(string)[0]))
    print(get_longest_palindromes(string)[0])
except:
    pass

'''
Using even odd approach
'''

length=int(input())
s=input()

low, high, maxlen = 0, 0, 1
for i in range(1,length):
    #even length substring palindrome check
    low = i - 1
    high = i
    while low>=0 and high<length and s[low] == s[high]:
        #while it does not overflow and palindrome property do:
        if high-low+1>maxlen:
            start, maxlen = low, high - low +1
            #start for marking longest palindromes index
            #updating maxlen as new longest palindromic strings length 
        low-=1
        high+=1
        #size increases


    #odd length substring palindrome check
    low = i-1
    high = i+1
    while low>=0 and high<length and s[low]==s[high]:
        #while it does not overflow and palindrome property do:
        if high - low +1 > maxlen:
            start, maxlen = low, high - low + 1
            #start for marking longest palindromes index
            #updating maxlen as new longest palindromic strings length
        low-=1
        high+=1
print(maxlen)
print(s[start:start+maxlen])




def pal(string):
    for k in range(len(string) // 2):
        if string[k] != string[len(string) - (k + 1)]: return False
    return True


n = int(input())
s = input()

if s == s[::-1]:
    print(len(s))
    print(s)
else:
    out = ''
    maxLen = 0
    for i in range(n):
        for j in range(n):
            if i +j > n: break
            cur = s[i: i + j]
            if len(cur) > maxLen and pal(cur):
                out = cur
                maxLen = len(cur)
            else: pass
    print(maxLen)
    print(out)

n = int(input())
s = input()

if s == s[::-1]:
    print(len(s))
    print(s)
else:
    out = ''
    maxLen = 0
    for i in range(n):
        for j in range(n):
            if i +j > n: break
            cur = s[i: i + j]
            if len(cur) > maxLen and cur == cur[::-1]:
                out = cur
                maxLen = len(cur)
            else: pass
    print(maxLen)
    print(out)

n = int(input())
s = input()

if s == s[::-1]:
    print(len(s))
    print(s)
else:
    out = ''
    maxLen = 0
    for i in range(n):
        for j in range(n):
            cur = s[i: n - j]
            if cur != out and len(cur) > maxLen and cur != '' and cur == cur[::-1]:
                out = cur
                maxLen = len(cur)
            else: pass
    print(maxLen)
    print(out)


n = int(input())
s = input()

if s == s[::-1]:
    print(len(s))
    print(s)
else:
    out = ''
    maxLen = 0
    for i in range(n):
        for j in range(n):
            cur = s[i: i + j]
            if cur != out and len(cur) > maxLen and cur != '' and cur == cur[::-1]:
                out = cur
                maxLen = len(cur)
            else: continue
    print(maxLen)
    print(out)


def rev(arr):
    cop = arr.copy()
    cop.reverse()
    return cop
try:
    n = int(input())
    s=[]
    ans =[]
    data = list(input())
    for i in range(n):
        s.append(data[i])
        for j in range(i+1,n):
            s.append(data[j])
            if(s == rev(s)):
                ans.append(''.join(rev(s)))
        s.clear()
        
    r = max(ans,key=len)
    print(len(r))
    print(r)
except:
    pass

def palin(s):
    if s == s[::-1]:
        return 'YES'
    else:
        return 'NO'
try:
    N = int(input())
    S = input()
    es = [S[i: j] for i in range(len(S)) for j in range(i + 1, len(S) + 1)]
    length = 1
    b = S[0]
    for i in es:
        a = palin(i)
        if a == 'YES':
            if len(i) > length:
                length = len(i)
                b = i
        else:
            pass
    print(length)
    print(b)
except:
    pass



n= int(input())
s=input()
s1 = set([s[i: j] for i in range(len(s)) 
          for j in range(i + 1, len(s) + 1)])
          
for val in sorted(s1,key= len ,reverse=True):
    if(val==val[::-1]):
        print(len(val))
        print(val)
        break

# cook your dish here
int(input())
test_str = input() 
#Find all unique substrings in a given string
res = set([test_str[i: j] for i in range(len(test_str)) 
          for j in range(i + 1, len(test_str) + 1)])

for val in sorted(res,key = len,reverse=True):
    if val == val [::-1]:
        print(len(val))
        print(val)
        break


from itertools import combinations
N = int(input())
st = input()
mx = ""
a = [st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)] 
for i in a:
    for j in range(len(i)//2 + 1):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        if len(mx) < len(i):
            mx = i
print(len(mx))
print(mx)

from itertools import combinations
N = int(input())
st = input()
mx = ""
ans = False
a = [st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)] 
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        if len(mx) < len(i):
            mx = i
print(len(mx))
print(mx)

from itertools import combinations

N = int(input())
st = input()
n = len(st)
mx = ""
ans = False
a = [st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)] 
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        if len(mx) < len(i):
            mx = i
print(len(mx))
print(mx)

from itertools import combinations

N = int(input())
st = input()
n = len(st)
mx = ""
ans = False
a = set({st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)})
a = list(a)
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        if len(mx) < len(i):
            mx = i
print(len(mx))
print(mx)

from itertools import combinations

N = int(input())
st = input()
n = len(st)
mx = []
ans = False
a = set({st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)})
a = list(a)
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        mx.append(i)

m = max(mx, key=len)
print(len(m))
print(m)

from itertools import combinations

N = int(input())
st = input()
n = len(st)
mx = []
ans = False
a = [st[x:y] for x, y in combinations(range(len(st) + 1), r = 2)] 
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        mx.append(i)

m = max(mx, key=len)
print(len(m))
print(m)

N = int(input())
st = input()
n = len(st)
a = []
mx = []
ans = False
for i in range(n):
    for j in range(i+1,n+1):
        if st[i:j] not in a:
            a.append(st[i:j])
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        mx.append(i)
m = max(mx, key=len)
print(len(m))
print(m)
            


N = int(input())
st = input()
n = len(st)
a = set()
mx = []
ans = False
for i in range(n):
    for j in range(i+1,n+1):
        a.add(st[i:j])
a = list(a)
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        mx.append(i)
m = max(mx, key=len)
print(len(m))
print(m)
            


N = int(input())
st = input()
n = len(st)
a = set()
mx =[]
ans = False
for i in range(n):
    for j in range(i+1,n+1):
        a.add(st[i:j])
a = list(a)
for i in a:
    for j in range(len(i)//2):
        if i[j]==i[-1-j]:
            ans = True
        else:
            ans = False
            break
    if ans == True:
        mx.append(i)
    else:
        continue
m = max(mx, key=len)
print(len(m))
print(m)
            


n = int(input())
a = input()
b = a[::-1]
c = [[0 for k in range(n+1)] for l in range(n+1)]
m = 0
index = -1
# print(a)
# print(b)
# print(c)
for i in range(n+1):
    for j in range(n+1):
        if(i==0 or j==0):
            c[i][j] = 0
        elif(a[i-1] == b[j-1]):
            c[i][j] = 1+c[i-1][j-1]
            if(c[i][j]>m):
                m = c[i][j]
                index = i
        else:
            c[i][j] = 0

print(m)
print(b[n-index:n-index+m])
# print(c)
# print(index-1)
# print(m)


# cook your dish here
def pal(str):
    h=len(str)//2
    i=0
    j=len(str)-1
    for k in range(h):
        if(str[i]!=str[j]):
            return False
        i=i+1
        j=j-1
    return True
n=int(input())
s=(input())
max=0
for i in range(1,n+1):
    for j in range(0,n):
        if(j+i > n):
            break;
        str=s[j:j+i]
        if(pal(str) and len(str)>max):
            max=len(str)
            l=str
print(max)
print(l)
            
    


# cook your dish here
def pal(str):
    h=len(str)//2
    i=0
    j=len(str)-1
    for k in range(h):
        if(str[i]!=str[j]):
            return False
        i=i+1
        j=j-1
    return True
n=int(input())
s=list(input())
max=0
for i in range(1,n+1):
    for j in range(0,n):
        if(j+i > n):
            break;
        str=s[j:j+i]
        if(pal(str) and len(str)>max):
            max=len(str)
            l=str
print(max)
for i in l:
    print(i,end='')
print('')