make-the-cheapest-palindrome-1
Source: hackerearth
Difficulty: MEDIUM

Palindrome is a string that reads the same backward as forward, e.g., madam. 

You are given a string whose length  is even, and each character of the string is either 'a', 'b' or '/' Your task is to replace each occurrence of '/' in string with either 'a' or 'b' such that the string becomes a palindrome. 

You are also given two integers, aCost and bCost. Replacing '/' with 'a' costs aCost, and replacing '/' with 'b' costs bCost.

Return the minimum cost of replacing '/' by 'a' and 'b' such that the string turns into a palindrome. If it is impossible to obtain a palindrome, return -1.

Constraints
string will contain between 1 and 10000 characters, inclusive.
The length of string will be even.
Each character of the string will be either 'a' or 'b' or '/'.
aCost will be between 1 and 100, inclusive.
bCost will be between 1 and 100, inclusive.

Input Format

First line of input will contain the number of test cases.
For each test case, there will be of three lines, the first line is the string whose palindrome is to be constructed, the second is the aCost and the third is the bCost

Examples

1

aba/bab/

4

6

Returns: 10

The only way to produce a palindrome is to replace 4th character of string with 'b' and 8th character with 'a'. The first replacement costs 4, the second costs 6, so the total cost is 4+6=10.

aaaabbbb

12

34

Returns: -1

There is no '/' character, and string is not a palindrome. We have no way to change it into a palindrome.

SAMPLE INPUT
1
baba//aaa/ab//
72
23

SAMPLE OUTPUT
213


for _ in range(eval(input())):
	s = input()
	a = eval(input())
	b = eval(input())
	e = len(s)-1
	sm = 0
	flag = 0
	for i in range(len(s)/2):
		if s[i]!=s[e] and s[i] != '/' and s[e] != '/':
			print('-1')
			e = e-1
			flag = 1
			break
		else:
			if s[i] == s[e] and s[i] == '/':
				if a < b: sm = sm + 2*a
				else: sm = sm + 2*b
			else:
				if s[i] == '/':
					if s[e] == 'a':
						sm = sm+a
					else:
						sm = sm + b
				else:
					if s[e] == '/':
						if s[i] == 'a':
							sm = sm+a
						else:
							sm = sm + b
		e = e-1
	if not flag:
		print(sm)


def isPalind(a):
	return a==a[::-1]


for _ in range(eval(input())):
	s=input()
	Ca=eval(input())
	Cb=eval(input())
	ans = 0
	danger = 0
	for i in range(len(s)/2):
		if (s[i]=='/' and s[len(s)-1-i] =='/'):
			ans+=(2*(min(Ca,Cb)))
		elif s[i]=='/' and s[len(s)-1-i]!='/':
			if s[len(s)-1-i] == 'a':
					ans+=Ca
			else:
					ans+=Cb
		elif s[i]!='/' and s[len(s)-1-i]=='/':
			if s[i] == 'a':
					ans+=Ca
			else:
					ans+=Cb
		else:
				if (s[i]!=s[len(s)-i-1]):
					danger = 1
			
	print(-1 if danger else ans)
	


n = int(input())
for i in range(n) :
	s = input()
	ac = int(input())
	bc = int(input())
	s = list(s)
	cost = 0
	for i in range(len(s)) :
		if s[i] == '/':
			if s[len(s) - i - 1] == 'a' :
				s[i] = 'a'
				cost = cost + ac
			elif s[len(s) - i - 1 ] == 'b' :
				s[i] = 'b'
				cost = cost + bc
			else :
				if ac < bc :
					s[i] = 'a'
					cost = cost + ac
				else :
					s[i] = 'b'
					cost = cost + bc
					
	for j in range(len(s)):
		if s[j] != s[len(s) - j -1]:
			cost = -1
			break
			
	print(cost)


N = int(input())

def get_cost(name, ac, bc):
	cost = 0
	cheap = ac if ac<bc else bc
	m = len(name)/2
	b = -1
	for f in range(m):
		if '/' in [name[f], name[b]]:
			if name[f] == name[b]:
				cost += 2*cheap
			else:
				h = b if name[f]=='/' else f
				cost += ac if name[h]=='a' else bc
		else:
			if name[f] != name[b]:
				cost = -1
				break
		b = b-1
	return cost

for i in range(N):
	name = input()
	ac = int(input())
	bc = int(input())
	
	print(get_cost(name, ac, bc))



test=eval(input())
for i in range(test):
	listtt=input()
	acost=eval(input())
	bcost=eval(input())
	if acost<bcost:
		lcost=acost
	else:
		lcost=bcost	
	last=len(listtt)-1
	first=0
	flag=0
	totalcost=0
	while first<last:
		if listtt[first]=='/' and listtt[last]=='/':
			totalcost+=2*lcost
		elif listtt[first]=='/' and listtt[last]=='a':
			totalcost+=acost
		elif listtt[first]=='/' and listtt[last]=='b':
			totalcost+=bcost
		elif listtt[last]=='/' and listtt[first]=='a':
			totalcost+=acost
		elif listtt[last]=='/' and listtt[first]=='b':
			totalcost+=bcost
		elif listtt[first]!=listtt[last]:
			flag=1
			break
		first=first+1
		last=last-1
	if flag==1:
		print('-1')
	else:
		print(totalcost) 
			


def getcost(name):
	c=0
	i=0
	l=len(name)
	f=1
	while i < l/2:
		    #print "%c %c"%(name[i],name[l-i-1])
		    if   name[i] !=name[l-i-1] and name[i]!='/' and name[l-i-1] !='/':
		    	return -1 #nothing can be done so gtfo
		    elif name[i] =='/' and name[l-i-1]=='a':  #left slot is empty and right is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='a' and name[l-i-1]=='/':  #right slot is empty and left is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1] == 'b':  #left slot is empty and right is b
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='b' and name[l-i-1] == '/':  #right slot is empty and right is empty
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1]=='/': #both slots are empty
		        cost = 2*acost if acost<bcost else 2*bcost
		        c+=cost;
		        #print "added %d "%cost
		    
		    i += 1

	return c

#print "starting"
n=int(input())
while (n>0):
	name=input()
	acost=int(input())
	bcost=int(input())
	c=getcost(name)
	print(c)
	n=n-1


def test(S,aCost,bCost):
	if S.count('/')== 0 and not palindrome(S):
		print(-1)
	else:
		cost=0
		counter=0
		l=len(S)
		while counter < l/2:            
			if S[counter] != S[l-counter-1]:
				if S[counter]=='/':
					if S[l-counter-1]=='a':
						S=S[:counter] + 'a' + S[counter+1:]
						cost+=aCost
					else:
						S=S[:counter] + 'b' + S[counter+1:]
						cost+=bCost
				elif S[l-counter-1]=='/':
					if S[counter]=='a':
						S=S[:l-counter-1] + 'a' + S[l-counter:]
						S=S.replace(S[l-counter-1],'a')
						cost+=aCost
					else:
						S=S[:l-counter-1] + 'b' + S[l-counter:]
						cost+=bCost
			elif S[counter] == '/':
				if aCost < bCost:
					S=S[:l-counter-1] + 'a' + S[l-counter:]
					S=S[:counter] + 'a' + S[counter+1:]
					cost+= aCost*2
				else:
					S=S[:l-counter-1] + 'b' + S[l-counter:]
					S=S[:counter] + 'b' + S[counter+1:]
					cost+= bCost*2
			counter+=1
		if not palindrome(S):
			print(-1)
		else:
			print(cost)

def palindrome(s):
	isp=True
	counter=0
	l=len(s)
	while counter < l:
		if s[counter] != s[l-counter-1]:
			isp=False
			break
		counter+=1
	return isp




t = int(input())
counter=0
while counter < t:
	S= input()
	aCost= int(input())
	bCost= int(input())
	test(S,aCost,bCost)
	counter+=1



t=int(input())
while t:
	t=t-1
	s=input()
	ac=int(input())
	bc=int(input())
	total=0
	i=0
	j=len(s)-1
	while(i<j):
		#print i,j,start,end,
		start=s[i]
		end=s[j]  
		if(start=='/' and end=='/'):
				total=total+ 2*min(ac,bc)
		if(start!=end):
			if(start=='/'):
				if(end=='b'):
					total=total+bc
				else:
					total=total+ac
			elif(end=='/'):
				if(start=='b'):
					total=total+bc
				else:
					total=total+ac
			else:
				total=0
				i=i+j
		i+=1
		j-=1      
		#print total
	if(total>0):
		print(total)
	else:
		print(-1)
			
		


import sys
for w in range(eval(input())):
	cost=0
	d=1
	string=input()
	acost=eval(input())
	bcost=eval(input())
	if acost<=bcost:
		low=acost
	else:
		low=bcost
	l=len(string)
	str1=string[:(l+1)/2]
	str2=string[(l+1)/2:][::-1]
	for i,j in zip(str1,str2):
		if i=='/' and j=='/':
			cost += 2*low
		elif i=='/' or j=='/':
			if i=='/':
				if j=='a':
					cost += acost
				else:
					cost += bcost
			elif j=='/':
				if i=='a':
					cost += acost
				else:
					cost += bcost
		else:
			if i!=j:
				d=0
	if(d==0):
		cost= -1
	print(cost)
				
		



	



def getcost(name):
	c=0
	i=0
	l=len(name)
	f=1
	while i < l/2:
		    #print name[i]
		    if   name[i] != name[l-i-1] and name[i]!='/' and name[l-i-1] !='/':
		    	return -1 #nothing can be done so gtfo
		    elif name[i] =='/' and name[l-i-1]=='a':  #left slot is empty and right is full
		        c+=acost;
		    elif name[i] =='/' and name[l-i-1] == 'b':  #left slot is empty and right is full
		        c+=bcost;
		    elif name[i] =='a' and name[l-i-1]=='/':  #right slot is empty and       left is full
		        c+=acost;
		    elif name[i] =='b' and name[l-i-1]=='/':  #right slot is empty and       left is full
		        c+=bcost;
		        
		    elif name[i] =='/' and name[l-i-1]=='/': #both slots are empty
		        c+=2*acost if acost<bcost else 2*bcost   #select the lowest cost
		    i += 1

	return c

#print "starting"
n=int(input())
while (n>0):
	name=input()
	acost=int(input())
	bcost=int(input())
	c=getcost(name)
	print(c)
	n=n-1


for _ in range(int(input())):
	s = input()
	l = len(s) / 2
	ac, bc = int(input()), int(input())
	c = {"a":ac, "b":bc}
	if ac < bc:
		mc = ac
		ms = "a"
	else:
		mc = bc
		ms = "b"
	s1 = list(s[:l])
	s2 = list(s[l:][::-1])
	ans = 0
	for i in range(l):
		if s1[i] == "/":
			if s2[i] == "/":
				ans += 2 * mc
				s1[i] = ms
				s2[i] = ms
			else:
				ans += c[s2[i]]
				s1[i] = s2[i]
		elif s2[i] == "/":
			ans += c[s1[i]]
			s2[i] = s1[i]
	if s1 == s2:		
		print(ans)
	else:
		print(-1)
			


def getcost(name):
	c=0
	i=0
	l=len(name)
	f=1
	while i < l/2:
		    #print "%c %c"%(name[i],name[l-i-1])
		    if   name[i] !=name[l-i-1] and name[i]!='/' and name[l-i-1] !='/':
		    	return -1 #nothing can be done so gtfo
		    elif name[i] =='/' and name[l-i-1]=='a':  #left slot is empty and right is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='a' and name[l-i-1]=='/':  #right slot is empty and left is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1] == 'b':  #left slot is empty and right is b
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='b' and name[l-i-1] == '/':  #right slot is empty and right is empty
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1]=='/': #both slots are empty
		        cost = 2*acost if acost<bcost else 2*bcost
		        c+=cost;
		        #print "added %d "%cost
		    
		    i += 1

	return c

#print "starting"
n=int(input())
while (n>0):
	name=input()
	acost=int(input())
	bcost=int(input())
	c=getcost(name)
	print(c)
	n=n-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
# ignore the first line
sys.stdin.readline()
line = sys.stdin.readline()
while line:
	string = line.strip()
	acost = int(sys.stdin.readline().strip())
	bcost = int(sys.stdin.readline().strip())
	i = 0
	j = len(string) - 1
	psb = True
	cost = 0
	while i < j:
		if (string[i] != string[j]) and (string[i] != '/' and string[j] != '/'):
			psb = False
			break
		elif (string[i] == string[j]) and (string[i] != '/' and string[j] != '/'):
			i += 1
			j -= 1
			continue
		elif string[i] == '/' and string[j] == '/':
			if acost < bcost:
				cost += 2 * acost
			else:
				cost += 2 * bcost
		else:
			if string[i] != '/':
				if string[i] == 'a':
					cost += acost
				else:
					cost += bcost
			elif string[j] != '/':
				if string[j] == 'a':
					cost += acost
				else:
					cost += bcost
		i += 1
		j -= 1
	if psb:
		print(cost)
	else:
		print(-1)

	line = sys.stdin.readline()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def na(p):
	ans=0
	m=len(p)
	for i in range(m):
		if(z[i]=='/'):
			if(z[m-i-1]=='a'):
				z[i]='a'
				ans+=a
			elif(z[m-i-1]=='b'):
				z[i]='b'
				ans+=b
			else:
				if(a<b):
					z[i]='a'
					ans+=a
				else:
					z[i]='b'
					ans+=b
	for i in range(m):
		if(z[i]!=z[m-i-1]):
			ans=-1
			break
	return ans
	


for _ in range(eval(input())):
	z=list(input())
	a=int(input())
	b=int(input())
	m=len(z)
	
	print(na(z))	



test_cases = int(input())
for t in range(test_cases):
	org_str = input()
	l =len(org_str)
	a_cost = int(input())
	b_cost = int(input())
	min_cost=0
	for i,c in enumerate(org_str[:l/2]):
		if c=="a":
			if org_str[l-i-1]=="/":
				min_cost+=a_cost
			elif org_str[l-i-1]=="b":
				min_cost=-1
				break
		elif c=="b":
			if org_str[l-i-1]=="/":
				min_cost+=b_cost
			elif org_str[l-i-1]=="a":
				min_cost=-1
				break
		else:
			if org_str[l-i-1]=="a":
				min_cost+=a_cost
			elif org_str[l-i-1]=="b":
				min_cost+=b_cost
			else:
				if a_cost < b_cost:
					min_cost+=2*a_cost
				else:
					min_cost+=2*b_cost
	print(min_cost)
			


def getcost(name):
	c=0
	i=0
	l=len(name)
	f=1
	while i < l/2:
		    #print "%c %c"%(name[i],name[l-i-1])
		    if   name[i] !=name[l-i-1] and name[i]!='/' and name[l-i-1] !='/':
		    	return -1 #nothing can be done so gtfo
		    elif name[i] =='/' and name[l-i-1]=='a':  #left slot is empty and right is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='a' and name[l-i-1]=='/':  #right slot is empty and left is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1] == 'b':  #left slot is empty and right is b
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='b' and name[l-i-1] == '/':  #right slot is empty and right is empty
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1]=='/': #both slots are empty
		        cost = 2*acost if acost<bcost else 2*bcost
		        c+=cost;
		        #print "added %d "%cost
		    
		    i += 1

	return c

#print "starting"
n=int(input())
while (n>0):
	name=input()
	acost=int(input())
	bcost=int(input())
	c=getcost(name)
	print(c)
	n=n-1


def calcCheapest(s, a, b):
	cost = 0
	for i in range(len(s)):
		if s[i] == "/":
			
			if s[len(s)-i - 1] == "/":
				if a < b:
					s[i] = s[len(s) - i - 1] = 'a'
					cost += 2 * a
				else:
					s[i] = s[len(s)-i - 1] = 'b'
					cost += 2 * b
			else:
				s[i] = s[len(s)-i - 1]
				if s[len(s)-i - 1] == 'a':
					cost += a
				else:
					cost += b
		else:
			if s[i] == 'a':
				if s[len(s)-i - 1] == 'b':
					return -1
				else:
					if s[len(s)-i - 1] == '/':
						s[len(s)-i - 1] = 'a'
						cost += a
			if s[i] == 'b':
				if s[len(s)-i - 1] == 'a':
					return -1
				elif s[len(s)-i - 1] == "/":
					s[len(s)-i - 1] = 'b'
					cost += b
	return cost

for _ in range(eval(input())):
	s = input().strip()
	a = eval(input())
	b = eval(input())
	print(calcCheapest(list(s), a, b))
					
		


for _ in range(int(input())):
	str = input()
	a = int(input())
	b = int(input())
	mid = len(str)/2
	opt = min(a,b)
	l = len(str)
	count = 0
	for i in range(mid):
		if str[i] !=str[l-i-1] and str[i]!='/' and str[l-i-1] !='/':
			count=-1
			break
		if str[i]=='/' and str[l-1-i]=='/':
			count+= (opt*2)
		elif str[l-1-i] == 'a' and str[i]=='/':
			count  += a
		elif str[l-1-i] == 'b' and str[i]=='/':
			count  += b
		elif str[l-1-i] == '/' and str[i]=='a':
			count  += a
		elif str[l-1-i] == '/' and str[i]=='b':
			count  += b
	print(count)


def test(S,aCost,bCost):
	if S.count('/')== 0 and not palindrome(S):
		print(-1)
	else:
		cost=0
		counter=0
		l=len(S)
		L=list(S)
		while counter < l/2:            
			if S[counter] != S[l-counter-1]:
				if S[counter]=='/':
					if S[l-counter-1]=='a':
						L[counter]='a'
						cost+=aCost
					else:
						L[counter]='b'
						cost+=bCost
				elif S[l-counter-1]=='/':
					if S[counter]=='a':
						L[l-counter-1]='a'                                                
						cost+=aCost
					else:
						L[l-counter-1]='b'
						cost+=bCost
			elif S[counter] == '/':
				if aCost < bCost:
					L[counter]='a'
					L[l-counter-1]='a'
					cost+= aCost*2
				else:
					L[counter]='b'
					L[l-counter-1]='b'
					cost+= bCost*2
			counter+=1
		
		if not palindrome(''.join(L)):
			print(-1)
		else:
			print(cost)

def palindrome(s):
	isp=True
	counter=0
	l=len(s)
	while counter < l:
		if s[counter] != s[l-counter-1]:
			isp=False
			break
		counter+=1
	return isp




t = int(input())
counter=0
while counter < t:
	S= input()
	aCost= int(input())
	bCost= int(input())
	test(S,aCost,bCost)
	counter+=1



def getcost(name):
	c=0
	i=0
	l=len(name)
	f=1
	while i < l/2:
		    #print "%c %c"%(name[i],name[l-i-1])
		    if   name[i] !=name[l-i-1] and name[i]!='/' and name[l-i-1] !='/':
		    	return -1 #nothing can be done so gtfo
		    elif name[i] =='/' and name[l-i-1]=='a':  #left slot is empty and right is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='a' and name[l-i-1]=='/':  #right slot is empty and left is a
		        cost=acost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1] == 'b':  #left slot is empty and right is b
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    elif name[i] =='b' and name[l-i-1] == '/':  #right slot is empty and right is empty
		        cost=bcost;
		        c+=cost;
		        #print "added %d "%cost
		    
		    elif name[i] =='/' and name[l-i-1]=='/': #both slots are empty
		        cost = 2*acost if acost<bcost else 2*bcost
		        c+=cost;
		        #print "added %d "%cost
		    
		    i += 1

	return c

#print "starting"
n=int(input())
while (n>0):
	name=input()
	acost=int(input())
	bcost=int(input())
	c=getcost(name)
	print(c)
	n=n-1


test = int(eval(input()))
for t in range(test):
	s = list(input())
	c = 0
	cc= 0
	ccc=0
	flag = 0
	acost = eval(input())
	bcost = eval(input())
	if acost<=bcost:
		chhota = acost
		bada = bcost
	else:
		chhota = bcost
		bada = acost
	i = 0
	j = len(s)-1
	while(i<j):
		if(s[i]=='/' and s[j]=='a'):
			s[i] = 'a'
			c = c + acost
		elif(s[i]=='a' and s[j]=='/'):
			s[j] = 'a'
			c = c + acost
		elif(s[i]=='/' and s[j]=='b'):
			s[i] = 'b'
			cc = cc + bcost
		elif(s[i]=='b' and s[j]=='/'):
			s[j] = 'b'
			cc = cc + bcost
		elif(s[i]=='/' and s[j]=='/'):
			ccc = ccc + (2*chhota)
		elif((s[i] != '/' or s[j]!='/') and s[i] != s[j]):
			flag = 1
		i = i + 1
		j = j - 1
	if(flag == 1):
		print(-1)
		continue
	sum1 = c + cc + ccc
	print(sum1)



def cost(sttr,ac,bc):
	lo = 0;
	hi = len(sttr)-1;
	
	cost = 0;
	possible = 1;
	
	while(lo < hi):
		if( (sttr[lo] != '/') and (sttr[hi] != '/') and (sttr[lo] != sttr[hi]) ):
			possible = -1;
			break;
		elif( ( sttr[lo] == sttr[hi] ) and (sttr[lo] != '/') and (sttr[hi] != '/') ):
			lo = lo+1;
			hi = hi-1;
			continue;

		elif( (sttr[lo] == '/') and (sttr[hi] == '/') ):
			cost = cost + 2*min(ac,bc);
			lo = lo+1;
			hi = hi-1;
			continue;

		elif ( sttr[lo] == '/'):
			if(sttr[hi] == 'a'):
				cost = cost + ac;
				lo = lo+1;   hi = hi-1;
				continue;

			if(sttr[hi] == 'b'):
				cost = cost + bc;
				lo = lo+1;   hi = hi-1;
				continue;

		elif(sttr[hi] == '/'):
			
			if( sttr[lo] == 'a'):
				cost = cost + ac;
				lo = lo+1;   hi = hi-1;
				continue;

			if(sttr[lo] == 'b'):
				cost = cost + bc;
				lo = lo+1;   hi = hi-1;
				continue;

	return (possible,cost);

T = int(input());
while(T>0):
	sttr = input();
	ac = int(input());
	bc = int(input());
	(p,c) = cost(sttr,ac,bc);
	if(p == -1):
		print(p);
	else:
		print(c);
	T = T-1;


t=int(input())
for i in range(t):
	st=input()
	l=len(st)
	a=int(input())
	A=0
	b=int(input())
	B=0
	cost=0
	c=0
	for j in range(l//2):
		if st[j]!='/' and st[-j-1]!='/'and st[j]!=st[-j-1]:
			c=1
		else:
		    if st[j]==st[-j-1]:
				if st[j]=='/':
					cost=cost+min(a,b)*2
		
			elif st[j]=='a' or st[-j-1]=='a':
				cost=cost+a
			elif st[j]=='b'or st[-j-1]=='b':
				cost=cost+b
	if c==0:
		print(cost)
	else:
		print('-1');