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:

cabaacba

cabaacba

cabaacba

cabaacba

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.



Sample input:
4
cabaacba


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

S1 = list(S[:N])
# 左右同じものを目指す形にしたいので、片方はリバースしておく
S2 = list(S[N:])[::-1]

d1 = Counter()
d2 = Counter()
# 半分に分けた両方を組み合わせ全列挙
for i in range(1<<N):
    s1_1, s1_2 = [], []
    s2_1, s2_2 = [], []
    for j in range(N):
        if i>>j & 1:
            s1_1 += [S1[j]]
            s2_1 += [S2[j]]
        else:
            s1_2 += [S1[j]]
            s2_2 += [S2[j]]
    # 文字列ペアをキーとして、その通り数を数えておく
    d1[(''.join(s1_1), ''.join(s1_2))] += 1
    d2[(''.join(s2_1), ''.join(s2_2))] += 1

ans = 0
for k, v in d1.items():
    # 左文字列ペア = 右文字列ペア になるような通り数を数え上げる
    ans += v * d2[k]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    for i in range(n>>1):
      s[i],s[n-i-1] = s[n-i-1],s[i]
    d = defaultdict(lambda : 0)
    m = 1<<n
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j])
            else:
                b.append(s[j])
        d[(tuple(r),tuple(b))] += 1
        
    ans = 0
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j+n])
            else:
                b.append(s[j+n])
        ans += d[(tuple(r),tuple(b))]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    m = 1<<n
    p = [1<<j for j in range(n)]
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&p[j]:
                r.append(s[j])
            else:
                b.append(s[j])
        r,b = b[::-1],r[::-1]
        d[(tuple(r),tuple(b))] += 1

    ans = 0
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&p[j]:
                r.append(s[j+n])
            else:
                b.append(s[j+n])
        ans += d[(tuple(r),tuple(b))]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    m = 1<<n
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j])
            else:
                b.append(s[j])
        r,b = b[::-1],r[::-1]
        d[(tuple(r),tuple(b))] += 1
        
    ans = 0
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j+n])
            else:
                b.append(s[j+n])
        ans += d[(tuple(r),tuple(b))]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]

d = defaultdict(int)
ans = 0

def paint(str, ptn):
  red = ''.join(s for i, s in enumerate(str) if 2**i & ptn)
  blue = ''.join(s for i, s in enumerate(str) if not 2**i & ptn)
  return (red, blue)

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]
d = defaultdict(int)
ans = 0

def paint(str, ptn):
  red = ''.join(s for i, s in enumerate(str) if 2**i & ptn)
  blue = ''.join(s for i, s in enumerate(str) if not 2**i & ptn)
  return (red, blue)

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:]
S2 = S2[::-1]
rb1 = {}
rb2 = {}
for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r = ''
    b = ''
    for j in range(N):
        if flag[j] == '0':
            r += S1[j]
        else:
            b = S1[j] + b
    key = r + '&' + b
    if key in rb1.keys():
        rb1[key] += 1
    else:
        rb1[key] = 1

for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r = ''
    b = ''
    for j in range(N):
        if flag[j] == '0':
            r += S2[j]
        else:
            b = S2[j] + b
    key = r + '&' + b
    if key in rb2.keys():
        rb2[key] += 1
    else:
        rb2[key] = 1

ans = 0
for key in rb1.keys():
    if key in rb2.keys():
       ans += rb1[key] * rb2[key]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
S = input()

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = u = v = w = ""
    for j in range(N):
        if (i >> j) & 1:
            t += left[j]
            u += right[j]
        else:
            v += left[j]
            w += right[j]
    a[t, v] += 1
    b[u, w] += 1

print(sum(a[t] * b[t] for t in a.keys()))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
S = input()

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = "".join(left[j] if (i >> j) & 1 else "" for j in range(N))
    u = "".join(right[j] if (i >> j) & 1 else "" for j in range(N))
    v = "".join("" if (i >> j) & 1 else left[j] for j in range(N))
    w = "".join("" if (i >> j) & 1 else right[j] for j in range(N))
    a[t, v] += 1
    b[u, w] += 1

print((sum(a[t] * b[t] for t in a.keys())))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

S1, S2 = S[:N], S[N:][::-1]

dic = {}
keys = []
Ans = 0

for i in range(2 ** N):
    red, blue, red2, blue2 = "", "", "", ""
    # 半分ずつbit全探索
    bits = bin(2 ** N + i)[3:]
    for j in range(N):
        if bits[j] == "0":
            red += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    # あとで数える際に使うので記録しておく
    keys.append(red2 + "-" + blue2)
    # 半分全列挙
    key = red + "-" + blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for key in keys:
    Ans += dic.get(key, 0)

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(N):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
s=input()

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=list(itertools.product((0,1),repeat=N))

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a,blue_a)]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    key_reverse=(key[0][::-1],key[1][::-1])
    ANS+=STRA[key]*STRB[key_reverse]

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
l=s[:n]
r=s[n:][::-1]
d={}
e={}
for i in range(1<<n):
  s=t=u=v=''
  for j in range(n):
    if (i>>j)&1:
      s+=l[j]
      t+=r[j]
    else:
      u+=l[j]
      v+=r[j]
  d[(s,u)]=d.get((s,u),0)+1
  e[(t,v)]=e.get((t,v),0)+1
a=0
for i in d.keys():
  a+=d[i]*e.get(i,0)
print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

s1 = s[:n]
s2 = s[n:]

d1 = dict()
for i in range(1 << n):
    rd = ''
    bl = ''
    for j in range(n):
        if (i >> j) & 1:
            rd = rd + s1[j]
        else:
            bl = s1[j] + bl
    tpl = (rd, bl)
    d1[tpl] = d1.get(tpl, 0) + 1

d2 = dict()
for i in range(1 << n):
    rd = ''
    bl = ''
    for j in range(n):
        if (i >> j) & 1:
            rd = rd + s2[j]
        else:
            bl = s2[j] + bl
    tpl = (bl, rd)
    d2[tpl] = d2.get(tpl, 0) + 1

ans = 0
for k1, v1 in d1.items():
    ans += v1 * d2.get(k1, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n = int(input())
s = input()
ans = 0
for p in product([0,1], repeat=2*n):
    if p.count(1) != p.count(0):
        continue
    left = right = ""
    for j in range(2*n):
        if p[j]:
            left += s[j]
        else:
            right += s[j]
    right = right[-1::-1]
    if left == right:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n = int(input())
s = input()
ans = 0
for p in product([0,1], repeat=2*n):
    left = right = ""
    for j in range(2*n):
        if p[j]:
            left += s[j]
        else:
            right += s[j]
    right = right[-1::-1]
    if left == right:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

N = 2*n

ans = 0

def step(queue, ans):
    b = queue.pop(0)
    before = b[0]
    for i in range(b[1], b[2]):
        for j in range(i+1, b[2]):
            if s[i] == s[j]:
                queue.append([before + 2**i + 2**j, i+1, j])
    r = 0
    l = N-1
    while(True):
        while(l >= 0 and (before>>l) % 2 == 1):
            l-= 1
        while((before>>r) % 2 == 1):
            r+= 1
        if l < r:
            ans += 1
            break
            
        if l < b[1] or r >= b[2]:
            break
        
        if s[l] != s[r]:
            break
        l-=1
        r+=1
    return ans
        
queue = [[0, 0, N]]
while len(queue) > 0:
    ans = step(queue, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

N = 2*n

dp = [[0, N] for i in range(2**N)]

ans = 0

def step(queue, ans):
    before = queue.pop(0)
    for i in range(dp[before][0], dp[before][1]):
        for j in range(i+1, dp[before][1]):
            if s[i] == s[j]:
                after = before + 2**i + 2**j
                dp[after][0] = i+1
                dp[after][1] = j
                queue.append(after)
    r = 0
    l = N-1
    while(True):
        while(l >= 0 and (before>>l) % 2 == 1):
            l-= 1
        while((before>>r) % 2 == 1):
            r+= 1
        if l < r:
            ans += 1
            break
            
        if l < dp[before][0] or r >= dp[before][1]:
            break
        
        if s[l] != s[r]:
            break
        l-=1
        r+=1
    return ans
        
queue = [0]
while len(queue) > 0:
    ans = step(queue, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

sl = s[:n]
sr = s[n:][::-1]

from collections import Counter
l = Counter()
r = Counter()

from itertools import product
for m in product([False, True], repeat=n):
  key = [sl[i] for i in range(n) if not m[i]]
  key += ['-']
  key += [sl[i] for i in range(n) if m[i]]
  l[''.join(key)] += 1
  
  key = ''.join([sr[i] for i in range(n) if not m[i]])
  key += '-'
  key += ''.join([sr[i] for i in range(n) if m[i]])
  r[key] += 1
  
ans = sum(l[lk] * r[lk] for lk in l.keys())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    L[(T0,T1)]=L.get((T0,T1),0)+1
    R[(T2,T3)]=R.get((T2,T3),0)+1
for tup in L:
    ans+=L[tup]*R.get(tup,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    L[(T0,T1)]=L.get((T0,T1),0)+1
    R[(T2,T3)]=R.get((T2,T3),0)+1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    s1 = s[:n]
    s2 = s[n:][::-1]
    d1 = collections.defaultdict(int)
    d2 = collections.defaultdict(int)
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s1[j]
            else:
                t2 += s1[j]
        d1[t+t2] += 1
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s2[j]
            else:
                t2 += s2[j]
        d2[t+t2] += 1
    r = 0
    for k in d2.keys():
        r += d1[k] * d2[k]


    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
left = S[:N]
right = S[:N-1:-1]

# leftの(blue, red)のパターンを全列挙
br_pattern = defaultdict(int)

for bit in range(1<<N):
    blue = ""
    red = ""
    for isb in range(N):
        if bit & (1<<isb):
            blue = blue + left[isb]
        else:
            red = red + left[isb]
            
    br_pattern[(blue, red)] += 1

# rightの(red, blue)のパターンをひとつずつ調べ、br_patternに一致する数だけansに足す
ans = 0
for bit in range(1<<N):
    red = ""
    blue = ""
    for isr in range(N):
        if bit & (1<<isr):
            red = red + right[isr]
        else:
            blue = blue + right[isr]
            
    ans += br_pattern[(red, blue)]
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
    keys2 = [c[0]+'-'+c[1] for c in comb(sr)]
    cnt = 0
    for key1 in keys1:
        cnt += keys2.count(key1)
    return cnt
    '''
    dict = {}
    for t0, t1 in keys:
        key = t0 + '-' + t1
        cnt = has_key(sr, t0, t1)
        if key in dict:
            dict[key] += cnt
        else:
            dict[key] = cnt
    return sum(dict.values())
    '''


def comb(s):
    if len(s) == 1:
        return [(s, ''), ('', s)]
    else:
        ret = []
        for c in comb(s[0:len(s)-1]):
            ret.append((c[0]+s[-1], c[1]))
            ret.append((c[0], c[1]+s[-1]))
        return ret


'''
def has_key(s, t0, t1):
    cnt = 0
    if len(s) == 1:
        if s == t0:
            return 1
        elif s == t1:
            return 1
        else:
            return 0
    else:
        a = s[0]
        if len(t0) != 0 and a == t0[0]:
            cnt += has_key(s[1:len(s)], t0[1:len(t0)], t1)
        if len(t1) != 0 and a == t1[0]:
            cnt += has_key(s[1:len(s)], t0, t1[1:len(t1)])
    return cnt
'''


def read_line():
    n = int(input())
    s = input()
    return (n, s)


def main():
    n, s = read_line()
    print(run(n, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
    keys2 = [c[0]+'-'+c[1] for c in comb(sr)]
    cnt = 0
    for key1 in keys1:
        for key2 in keys2:
            if key1 == key2:
                cnt += 1
    return cnt
    '''
    dict = {}
    for t0, t1 in keys:
        key = t0 + '-' + t1
        cnt = has_key(sr, t0, t1)
        if key in dict:
            dict[key] += cnt
        else:
            dict[key] = cnt
    return sum(dict.values())
    '''


def comb(s):
    if len(s) == 1:
        return [(s, ''), ('', s)]
    else:
        ret = []
        for c in comb(s[0:len(s)-1]):
            ret.append((c[0]+s[-1], c[1]))
            ret.append((c[0], c[1]+s[-1]))
        return ret


'''
def has_key(s, t0, t1):
    cnt = 0
    if len(s) == 1:
        if s == t0:
            return 1
        elif s == t1:
            return 1
        else:
            return 0
    else:
        a = s[0]
        if len(t0) != 0 and a == t0[0]:
            cnt += has_key(s[1:len(s)], t0[1:len(t0)], t1)
        if len(t1) != 0 and a == t1[0]:
            cnt += has_key(s[1:len(s)], t0, t1[1:len(t1)])
    return cnt
'''


def read_line():
    n = int(input())
    s = input()
    return (n, s)


def main():
    n, s = read_line()
    print(run(n, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    dict = {}
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    keys = comb(sl)
    for t0, t1 in keys:
        key = t0 + '-' + t1
        cnt = has_key(sr, t0, t1)
        if key in dict:
            dict[key] += cnt
        else:
            dict[key] = cnt
    return sum(dict.values())


def comb(s):
    if len(s) == 1:
        return [(s, ''), ('', s)]
    else:
        ret = []
        for c in comb(s[0:len(s)-1]):
            ret.append((c[0]+s[-1], c[1]))
            ret.append((c[0], c[1]+s[-1]))
        return ret


def has_key(s, t0, t1):
    cnt = 0
    if len(s) == 1:
        if s == t0:
            return 1
        elif s == t1:
            return 1
        else:
            return 0
    else:
        a = s[0]
        if len(t0) != 0 and a == t0[0]:
            cnt += has_key(s[1:len(s)], t0[1:len(t0)], t1)
        if len(t1) != 0 and a == t1[0]:
            cnt += has_key(s[1:len(s)], t0, t1[1:len(t1)])
    return cnt


def read_line():
    n = int(input())
    s = input()
    return (n, s)


def main():
    n, s = read_line()
    print(run(n, s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N=int(input())
S=list(input())
S_rev=list(reversed(S[N:])) #右側から読んだ右半分の文字を考える

bit=list(product(range(2),repeat=N))
leftlist=[] #左半分の分け方の組み合わせを格納
rightlist=[] #右半分について同様

for i in range(len(bit)):
  red_left=''
  blue_left=''
  red_right=''
  blue_right=''
  for j in range(N):
    if bit[i][j] == 1:
      red_left+=S[j] #bitに1が立っているところを赤に
      blue_right+=S_rev[j]
    else:
      blue_left+=S[j]
      red_right+=S_rev[j]
  leftlist.append("".join(red_left + "|" + blue_left))
  rightlist.append("".join(blue_right + "|" + red_right))
left=Counter(leftlist)
right=Counter(rightlist)

answer=0

for key,value in left.items():
  answer+= value * right[key] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N=int(input())
S=list(input())
S_rev=list(reversed(S[N:]))

bit=list(product(range(2),repeat=N))
leftlist=[] #左半分の分け方の組み合わせを格納
rightlist=[] #右半分について同様

for i in range(len(bit)):
  red=''
  blue=''
  for j in range(N):
    if bit[i][j] == 1:
      red+=S[j] #bitに1が立っているところを赤に
    else:
      blue+=S[j]
  leftlist.append("".join(red + "|" + blue))
left=Counter(leftlist)
             
for i in range(len(bit)):
  red=''
  blue=''
  for j in range(N):
    if bit[i][j] == 1:
      blue+=S_rev[j]
    else:
      red+=S_rev[j]
  rightlist.append("".join(blue + "|" + red))
right=Counter(rightlist)

answer=0

for key,value in left.items():
  answer+= value * right[key] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for B in product(range(2),repeat = N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    for i in range(N):
        if int(B[i]):
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for B in product(range(2),repeat = N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    for i in range(N):
        if int(B[i]) == 1:
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for x in range(2**N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    B = bin(x)[2:]
    B = B.zfill(N)
    for i in range(N):
        if int(B[i]) == 1:
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dict_left = {}
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for x in range(2**N):
    red_left = ''
    blue_left = ''
    B = bin(x)[2:]
    B = B.zfill(N)
    for i in range(N):
        if int(B[i]) == 1:
            red_left += S_left[i]
        else:
            blue_left += S_left[i]
    tango = red_left + '|' + blue_left
    if tango in dict_left:
        dict_left[tango] += 1
    else:
        dict_left[tango] = 1
ans = 0
for x in range(2**N):
    red_right = ''
    blue_right = ''
    B = bin(x)[2:]
    B = B.zfill(N)
    for i in range(N):
        if int(B[i]) == 1:
            red_right += S_right[i]
        else:
            blue_right += S_right[i]
    tango = blue_right + '|' + red_right
    if tango in dict_left:
        ans += dict_left[tango]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())

import itertools
import copy

counter = 0
flag_list = [i for i in range(2*N)]
flag = itertools.combinations(flag_list, N)


for f in flag:
    red = ""
    s = copy.copy(S)
    for i in f:
        red += s[i]
        s[i] = "0"
    blue = "".join(s)[::-1].replace("0", "")
    if red == blue:
        counter += 1


print(counter)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0
for i in dict(s_1):
    '''
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[(sequence1, sequence1_inverse)] += 1     
    s_2[(sequence2, sequence2_inverse)] += 1
ans = 0

for i in dict(s_1):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[(sequence1, sequence1_inverse)] += 1     
    s_2[(sequence2, sequence2_inverse)] += 1
ans = 0
for i in dict(s_1):
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

sleft = S[:N]
sright = S[2*N:N-1:-1]
ldict,rdict = {},{}
count = 0
for i in range(2**N):
    red = bin(i)[2:].zfill(N)
    leftred, rightred, leftblue, rightblue = "","","",""
    for j in range(len(red)):
        if red[j] == "1":
            leftred += sleft[j]
            rightred += sright[j]
        else:
            leftblue += sleft[j]
            rightblue += sright[j]
    ldict[red] = leftred + "-" + leftblue
    rdict[red] = rightred + "-" + rightblue

for i in range(N+1):
    lchoose = set(v for k, v in ldict.items() if k.count("1") == i)
    rchoose = set(v for k, v in rdict.items() if k.count("1") == i)
    sameset = list(lchoose & rchoose)
    for j in range(len(sameset)):
        lnum = len(list(k for k, v in ldict.items() if v == sameset[j]))
        rnum = len(list(k for k, v in rdict.items() if v == sameset[j]))
        count += lnum * rnum
print(count)