import random, itertools, string, math
letters=string.ascii_lowercase
def eq_perm_cost_bruteforce_random(s):
n=len(s); h=n//2
A=s[:h]; B=s[h:]
best=math.inf
for maskA in range(1<<h):
for maskB in range(1<<h):
changedA=[bool(maskA&(1<<i)) for i in range(h)]
changedB=[bool(maskB&(1<<j)) for j in range(h)]
edges=[[False]*h for _ in range(h)]
for i in range(h):
for j in range(h):
if changedA[i] and changedB[j]:
edges[i][j]=True
elif changedA[i] and not changedB[j]:
edges[i][j
