Problem:
 Score : 600 points    Problem Statement You are given a string S of length 2N consisting of lowercase English letters.  There are 2^{2N} ways to color each character in S red or blue. Among these ways, how many satisfy the following condition?   The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left .       Constraints  1 \leq N \leq 18  The length of S is 2N .  S consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  N  S       Output Print the number of ways to paint the string that satisfy the condition.        Sample Input 1 4
cabaacba      Sample Output 1 4  There are four ways to paint the string, as follows:   c a b a a c b a  c a b a a c b a  c a b a a c b a  c a b a a c b a        Sample Input 2 11
mippiisssisssiipsspiim      Sample Output 2 504       Sample Input 3 4
abcdefgh      Sample Output 3 0       Sample Input 4 18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa      Sample Output 4 9075135300  The answer may not be representable as a 32 -bit integer.

Solution (Python):
import sys

if sys.version[0] == '2':
    range, input = xrange, raw_input

from collections import defaultdict
N = int(input())
S = input()
first, second = S[:N], S[N:]

s_set = defaultdict(int)

def make_str(bit, s):
    red = []
    blue = []
    for i in range(N):
        if bit >> i & 1:
            red.append(s[i])
        else:
            blue.append(s[i])
    return ''.join(red), ''.join(blue[::-1])

for bit in range(1 << N):
    s_set[make_str(bit, second)] += 1

ans = 0
for bit in range(1 << N):
    red, blue = make_str(bit, first)
    ans += s_set[blue, red]
print(ans)

Solution (Python):
from itertools import product
N = int(input())
S = input()
r = [0, 1]
ans = 0
d = [{} for i in range(N+1)]
for p in product(r, repeat=N):
    s = []
    for i in range(N):
        if p[i]:
            s.append(S[i])
    for i in range(N-1, -1, -1):
        if p[i] == 0:
            s.append(S[i])
    l = sum(p)
    s = "".join(s)
    d[l][s] = d[l].get(s, 0) + 1
for p in product(r, repeat=N):
    s = []
    for i in range(N-1, -1, -1):
        if p[i]:
            s.append(S[i+N])
    for i in range(N):
        if p[i] == 0:
            s.append(S[i+N])
    l = sum(p)
    s = "".join(s)
    ans += d[l].get(s, 0)
print(ans)

Solution (Python):

import sys

input=sys.stdin.readline

n=int(input())
s=input().strip()

memo={}
def getans(a,b,c):
    while a and c and a[0]==c[-1]:
        a=a[1:]
        c=c[:-1]
    if b=="":
        if a=="" and c=="": return 1
        else: return 0
    key=a+"/"+b+"/"+c
    if key in memo: return memo[key]
    
    ans=0
    for i in range(1,len(b)):
        if b[0]==b[i]:
            ans+=getans(a,b[1:i],b[i+1:]+c)
    
    ans+=getans(a+b[0],b[1:],c)
    memo[key]=ans
    
    return ans

print(getans("",s,"")*2)