Given a string, S.The string can contain small case English letters or '?'. You can replace '?' with any small English letter. Now if it is possible to make the string S a palindrome after replacing all '?' then find the palindromic string with a minimum ascii sum of the absolute difference of adjacent characters. Otherwise, return -1.
Example 1:
Input: S = a???c??c????
Output: 4
Explanation:
We can see that we can make the string
palindrome. Now to get minimum ascii sum we should
replace all the '?' between 'a' and 'c' with
'b' and all the '?' between two 'c' with 'c'.
So after replacing all the '?' the string: 
abbbccccbbba.
The sum of differences of adjacent characters is 4.   
Example 2:
Input: S = a???c??c???c
Output: -1
Explanation:
It is not possible to make the string palindrome.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimumSum() which takes a string S input parameter and returns an integer denoting the sum of differences of adjacent characters. If it is not possible to make string palindrome, return -1. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: import math

class Solution:

    def minimumSum(self, s : str) -> int:

        # code here

        



Solutions:
import math

class Solution:

	def minimumSum(self, s: str) -> int:
		l = len(s)
		if l % 2 == 0:
			i = int(l / 2) - 1
			f = int(l / 2)
		else:
			i = int((l - 1) / 2)
			f = int((l - 1) / 2)
		s = list(s)
		while i >= 0 and f < l:
			if s[i] == s[f] and s[i] != '?':
				i -= 1
				f += 1
				continue
			elif s[i] == s[f] and s[i] == '?':
				if i + 1 < f:
					s[i] = s[i + 1]
					s[f] = s[i + 1]
				else:
					k = i - 1
					m = f + 1
					while k >= 0 and m < l and (s[k] == '?') and (s[m] == '?'):
						k -= 1
						m += 1
					if m >= l:
						s[i] = 'a'
						s[f] = 'a'
					elif s[k] != '?':
						s[i] = s[k]
						s[f] = s[k]
					else:
						s[i] = s[m]
						s[f] = s[m]
			elif s[i] == '?' and s[f] != '?':
				s[i] = s[f]
			elif s[i] != '?' and s[f] == '?':
				s[f] = s[i]
			else:
				return -1
			i -= 1
			f += 1
		sum1 = 0
		i = 0
		l = len(s)
		while i < l - 1:
			sum1 = sum1 + abs(ord(s[i]) - ord(s[i + 1]))
			i = i + 1
		return sum1


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		rs = 0
		loopLength = math.ceil(len(s) / 2)
		lastChar = None
		for i in range(loopLength):
			if s[i] == s[-i - 1]:
				if s[i] != '?':
					if lastChar is not None:
						rs += 2 * abs(ord(s[i]) - ord(lastChar))
					lastChar = s[i]
			else:
				if s[i] != '?' and s[-i - 1] != '?':
					return -1
				agencyChar = s[i] if s[i] != '?' else s[-i - 1]
				if lastChar is not None:
					rs += 2 * abs(ord(agencyChar) - ord(lastChar))
				lastChar = agencyChar
		return rs


import math

class Solution:

	def minimumSum(self, string: str) -> int:
		char_list = []
		for char in string:
			char_list.append(char)
		n = len(char_list)
		for i in range(n // 2):
			if char_list[i] != '?' and char_list[n - 1 - i] != '?' and (char_list[i] != char_list[n - 1 - i]):
				return -1
		for i in range(n // 2):
			if char_list[i] == '?' and char_list[n - 1 - i] != '?':
				char_list[i] = char_list[n - 1 - i]
			elif char_list[i] != '?' and char_list[n - 1 - i] == '?':
				char_list[n - 1 - i] = char_list[i]
		char_stack = []
		i = 0
		while i < n:
			if char_list[i] != '?':
				char_stack.append(char_list[i])
				i = i + 1
			elif len(char_stack) >= 1:
				while i < n and char_list[i] == '?':
					char_list[i] = char_stack[len(char_stack) - 1]
					i = i + 1
				char_stack.pop()
			else:
				i = i + 1
		char_stack.clear()
		i = n - 1
		while i >= 0:
			if char_list[i] != '?':
				char_stack.append(char_list[i])
				i = i - 1
			elif len(char_stack) >= 1:
				while i < n and char_list[i] == '?':
					char_list[i] = char_stack[len(char_stack) - 1]
					i = i - 1
				char_stack.pop()
			else:
				i = i - 1
		for i in range(n):
			if char_list[i] == '?':
				char_list[i] = 'a'
		answer = 0
		for i in range(n - 1):
			d = abs(ord(char_list[i]) - ord(char_list[i + 1]))
			answer += d
		return answer


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		i = 0
		j = len(s) - 1
		ch = ' '
		while i <= j:
			if s[i] != '?':
				ch = s[i]
				break
			if s[j] != '?':
				ch = s[j]
				break
			i += 1
			j -= 1
		if ch == ' ':
			return 0
		i = 0
		j = len(s) - 1
		while i <= j:
			if s[i] != s[j] and s[i] != '?' and (s[j] != '?'):
				return -1
			elif s[i] == '?' and s[j] != '?':
				ch = s[j]
				s = s[0:i] + ch + s[i + 1:]
			elif s[i] != '?' and s[j] == '?':
				ch = s[i]
				s = s[0:j] + ch + s[j + 1:]
			elif s[i] == '?' and s[j] == '?':
				s = s[0:i] + ch + s[i + 1:j] + ch + s[j + 1:]
			else:
				ch = s[i]
				i += 1
				j -= 1
		c = 0
		for i in range(len(s) - 1):
			c += abs(ord(s[i]) - ord(s[i + 1]))
		return c


import math

class Solution:

	def minimumSum(self, s1: str) -> int:
		s = list(s1)
		size = len(s)
		half_size = size // 2
		for i in range(half_size):
			left = i
			right = size - i - 1
			left_is_wild = s[left] == '?'
			right_is_wild = s[right] == '?'
			if not left_is_wild and (not right_is_wild):
				if s[left] != s[right]:
					return -1
			else:
				if left_is_wild and (not right_is_wild):
					s[left] = s[right]
				if not left_is_wild and right_is_wild:
					s[right] = s[left]
		sum = 0
		i = 0
		while s[i] == '?' and i < half_size:
			i += 1
		next = i + 1
		while next <= half_size:
			if s[next] == '?':
				while s[next] == '?':
					next += 1
			diff = abs(ord(s[next]) - ord(s[i]))
			sum += diff
			i = next
			next += 1
		return 2 * sum


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		d = 0
		ch = 'NA'
		for i in range((len(s) + 1) // 2):
			if s[i] == s[len(s) - 1 - i] and s[i] != '?':
				if ch != s[i] and ch != 'NA':
					d = d + abs(ord(ch) - ord(s[i]))
				ch = s[i]
				continue
			elif s[i] == '?' and s[len(s) - 1 - i] != '?':
				if ch != s[len(s) - 1 - i] and ch != 'NA':
					d = d + abs(ord(ch) - ord(s[len(s) - 1 - i]))
				ch = s[len(s) - 1 - i]
			elif s[i] != '?' and s[len(s) - 1 - i] == '?':
				if ch != s[i] and ch != 'NA':
					d = d + abs(ord(ch) - ord(s[i]))
				ch = s[i]
			elif s[i] == '?' and s[len(s) - 1 - i] == '?':
				continue
			else:
				return -1
		return d * 2


import math

class Solution:

	def PossibleToMakePalindrome(self, s: str) -> bool:
		N = len(s)
		for i in range(N // 2):
			if s[i] != '?' and s[N - i - 1] != '?' and (s[i] != s[N - i - 1]):
				return False
		return True

	def minimumSum(self, s: str) -> int:
		if not self.PossibleToMakePalindrome(s):
			return -1
		N = len(s)
		for i in range(N // 2):
			if s[i] == '?' and s[N - i - 1] != '?':
				s = s[:i] + s[N - i - 1] + s[i + 1:]
			elif s[i] != '?' and s[N - i - 1] == '?':
				s = s[:N - i - 1] + s[i] + s[N - i:]
		NextChar = []
		i = 0
		while i < N:
			if s[i] != '?':
				NextChar.append(s[i])
				i += 1
			elif len(NextChar) >= 1:
				while i < N and s[i] == '?':
					s = s[:i] + NextChar[-1] + s[i + 1:]
					i += 1
				NextChar.pop()
			else:
				i += 1
		NextChar = []
		i = N - 1
		while i >= 0:
			if s[i] != '?':
				NextChar.append(s[i])
				i -= 1
			elif len(NextChar) >= 1:
				while i >= 0 and s[i] == '?':
					s = s[:i] + NextChar[-1] + s[i + 1:]
					i -= 1
				NextChar.pop()
			else:
				i -= 1
		for i in range(N // 2):
			if s[i] == '?' and s[N - i - 1] != '?':
				s = s[:i] + s[N - i - 1] + s[i + 1:]
			elif s[i] != '?' and s[N - i - 1] == '?':
				s = s[:N - i - 1] + s[i] + s[N - i:]
		s = s.replace('?', 'a')
		Ans = 0
		for i in range(N - 1):
			o = ord(s[i]) - ord('a')
			l = ord(s[i + 1]) - ord('a')
			Ans += abs(o - l)
		return Ans


import math

class Solution:

	def checkPalindrome(self, s: str) -> bool:
		n = len(s)
		front = 0
		back = n - 1
		while front <= back:
			if s[front] == s[back] or s[front] == '?' or s[back] == '?':
				front += 1
				back -= 1
			else:
				return False
		return True

	def replaceQuesMarks(self, s: str) -> str:
		n = len(s)
		front = 0
		back = n - 1
		newS = [s[i] for i in range(n)]
		while front <= back:
			if s[front] != s[back]:
				if s[front] == '?':
					newS[front] = s[back]
				else:
					newS[back] = s[front]
			front += 1
			back -= 1
		return ''.join(newS)

	def replaceAllQuesMarks(self, s: str) -> str:
		currFront = 0
		n = len(s)
		newS = [s[i] for i in range(n)]
		if newS[0] == '?':
			for i in range(n):
				if newS[i] != '?':
					newS[0] = newS[i]
					break
		if newS[0] == '?':
			newS = ['a' for i in range(n)]
			return ''.join(newS)
		for i in range(n - 1):
			if newS[i + 1] == '?':
				newS[i + 1] = newS[i]
			else:
				continue
		return ''.join(newS)

	def minimumSum(self, s: str) -> int:
		if not self.checkPalindrome(s):
			return -1
		newS = self.replaceQuesMarks(s)
		finalS = self.replaceAllQuesMarks(newS)
		count = 0
		n = len(s)
		for i in range(n - 1):
			diff = abs(ord(finalS[i + 1]) - ord(finalS[i]))
			count += diff
		return count


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		i = 0
		n = len(s)
		j = n - 1
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == '?':
				s = s[:i] + s[j] + s[i + 1:]
				i += 1
				j -= 1
			elif s[j] == '?':
				s = s[:j] + s[i] + s[j + 1:]
				i += 1
				j -= 1
			else:
				return -1
		ans = 0
		for i in range(n):
			if s[i] != '?':
				j = i + 1
				while j < n and s[j] == '?':
					j += 1
				if j < n:
					ans += abs(ord(s[j]) - ord(s[i]))
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		(sLeft, mod) = divmod(len(s), 2)
		sLeft -= 1
		sRight = sLeft + (mod + 1) % 2
		self.letters = []
		self.word = s
		continuous = self.iterate(sLeft, sRight)
		if continuous == -1:
			return -1
		return self.getDifference()

	def iterate(self, left, right):
		if left < 0:
			return
		if self.word[left] == self.word[right]:
			if self.word[left] != '?':
				self.letters.append(self.word[left])
		elif self.word[left] == '?':
			self.letters.append(self.word[right])
		elif self.word[right] == '?':
			self.letters.append(self.word[left])
		else:
			return -1
		return self.iterate(left - 1, right + 1)

	def getDifference(self):
		prev = None
		total = 0
		for char in self.letters:
			if prev is None:
				prev = char
				continue
			total += abs(ord(char) - ord(prev)) * 2
			prev = char
		return total


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		(i, j) = (0, len(s) - 1)
		count = 0
		while i < j:
			if s[i] != '?':
				count += 1
			if s[j] != '?':
				count += 1
			if s[i] != s[j] and (s[j] != '?' and s[i] != '?'):
				return -1
			elif s[i] != '?' and s[j] == '?':
				s = s[:j] + s[i] + s[j + 1:]
			elif s[i] == '?' and s[j] != '?':
				s = s[:i] + s[j] + s[i + 1:]
			i += 1
			j -= 1
		(l, ch, sum) = (len(s), '', 0)
		if count == 0 or count == 1:
			return 0
		for i in range(l):
			if s[i] != '?':
				ch = s[i]
				break
		for i in range(l):
			if s[i] != '?':
				ch = s[i]
			if s[i] == '?':
				if i <= l - 2:
					s = s[:i] + ch + s[i + 1:]
				else:
					s = s[:i] + ch
		for i in range(l - 1):
			sum += abs(ord(s[i]) - ord(s[i + 1]))
		return sum


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		l = [0] * len(s)
		if len(s) % 2 == 0:
			num = int(len(s) / 2)
		else:
			num = int((len(s) - 1) / 2)
			l[num] = ord(s[num])
		last = None
		for i in range(0, len(s)):
			if s[i] != '?':
				last = s[i]
				break
			if s[(i + 1) * -1] != '?':
				last = s[(i + 1) * -1]
				break
		if i == len(s) - 1 and s[i] == '?':
			return 0
		for i in range(0, num):
			if s[i] != s[(i + 1) * -1]:
				if s[i] != '?' and s[(i + 1) * -1] != '?':
					return -1
				if s[i] != '?':
					last = s[i]
				else:
					last = s[(i + 1) * -1]
				l[i] = l[(i + 1) * -1] = ord(last)
			else:
				if s[i] == '?' and s[(i + 1) * -1] == '?':
					l[i] = l[(i + 1) * -1] = ord(last)
					continue
				l[i] = l[(i + 1) * -1] = ord(s[i])
				last = s[i]
		count = 0
		for i in range(1, len(l)):
			count += abs(l[i] - l[i - 1])
		return count


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		res = 0
		last = -1
		s = [char for char in s]
		valQuest = ord('?')
		for (ind, char) in enumerate(s):
			a = s[ind]
			b = s[-(1 + ind)]
			if '?' not in [a, b]:
				if a != b:
					return -1
				if last != -1:
					res += abs(last - ord(a))
				last = ord(a)
			elif a == b == '?':
				continue
			else:
				value = ord(a) + ord(b) - ord('?')
				if last != -1:
					res += abs(last - value)
				last = value
		return res


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		ans = 0
		s = list(s)
		n = len(s)
		for i in range(n // 2):
			if s[i] == '?' and s[n - i - 1] != '?':
				s[i] = s[n - i - 1]
			elif s[i] != s[n - i - 1] and s[i] != '?' and (s[n - i - 1] != '?'):
				return -1
		prev = '.'
		for i in range(n // 2):
			if s[i] != '?':
				if prev == '.':
					prev = s[i]
				elif s[i] != prev:
					ans += abs(ord(s[i]) - ord(prev))
				prev = s[i]
		return ans * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		N = len(s)
		s = list(s)
		l = 0
		r = N - l - 1
		while l < r:
			if s[l] != '?' and s[r] != '?' and (s[l] != s[r]):
				return -1
			elif s[l] == '?':
				s[l] = s[r]
			else:
				s[r] = s[l]
			l += 1
			r = N - l - 1
		ans = 0
		prevInd = None
		for (ind, val) in enumerate(s):
			if val != '?':
				prevInd = ind
				prev = val
				break
		if prevInd == None:
			return 0
		for val in s[prevInd + 1:]:
			if val != '?':
				ans += abs(ord(val) - ord(prev))
				prev = val
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		res = 0
		c = ''
		n = len(s)
		for i in range(n):
			if s[i] != s[n - i - 1] and s[i] != '?' and (s[n - i - 1] != '?'):
				return -1
			elif s[i] != '?':
				if c == '':
					c = s[i]
				else:
					res += abs(ord(c) - ord(s[i]))
					c = s[i]
			elif s[n - i - 1] != '?':
				if c == '':
					c = s[n - i - 1]
				else:
					res += abs(ord(c) - ord(s[n - i - 1]))
					c = s[n - i - 1]
		return res


import math

class Solution:

	def minimumSum(self, s: str) -> int:

		def mirror(i):
			s[len(s) - 1 - i]
		chars = [c for c in s]
		(i, j) = (0, len(chars) - 1)
		while i < j:
			if chars[i] != chars[j]:
				if chars[i] == '?':
					chars[i] = chars[j]
				elif s[j] == '?':
					chars[j] = chars[i]
				else:
					return -1
			i += 1
			j -= 1
		n_over_2 = len(chars) // 2
		limit = n_over_2 - 1 if len(chars) % 2 == 0 else n_over_2
		i = 0
		while i <= limit and chars[i] == '?':
			i += 1
		prev = chars[i] if chars[i] != '?' else 'a'
		for i in range(0, limit + 1):
			if chars[i] == '?':
				chars[i] = prev
				chars[len(chars) - 1 - i] = chars[i]
			prev = chars[i]
		total = 0
		for i in range(1, len(chars)):
			total += abs(ord(chars[i]) - ord(chars[i - 1]))
		return total


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		center = len(s) // 2
		arr = []
		for c in s:
			arr.append(c)
		for i in range(len(s)):
			if arr[i] != '?' and arr[len(s) - i - 1] == '?':
				arr[len(s) - i - 1] = arr[i]
			elif arr[i] == '?' and arr[len(s) - i - 1] != '?':
				arr[i] = arr[len(s) - i - 1]
			elif arr[i] != '?' and arr[len(s) - i - 1] != '?':
				if arr[i] != arr[len(s) - i - 1]:
					return -1
		count = 0
		ch = 'A'
		for i in range(center + 1):
			if arr[i] != '?':
				if ch == 'A':
					ch = arr[i]
				else:
					if ord(ch) > ord(arr[i]):
						count += ord(ch) - ord(arr[i])
					else:
						count += ord(arr[i]) - ord(ch)
					ch = arr[i]
		return 2 * count


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		if len(set(s)) == 1:
			return 0
		check1 = s[::-1]
		troop = ''
		for i in range(len(s)):
			if s[i] != check1[i] and s[i] != '?' and (check1[i] != '?'):
				return -1
			elif s[i] == '?' and check1[i] != '?':
				troop += check1[i]
			elif s[i] != '?' and check1[i] == '?':
				troop += s[i]
			elif s[i] == check1[i] and s[i] != '?' and (check1[i] != '?'):
				troop += s[i]
			else:
				pass
		s = troop
		find = 0
		if len(s) == 2:
			return abs(ord(s[1]) - ord(s[0])) * 2
		for i in range(len(s) - 1):
			if i == 0:
				find += abs(ord(s[i + 1]) - ord(s[i]))
			elif i % 2 != 0:
				find += abs(ord(s[i - 1]) - ord(s[i]))
				find += abs(ord(s[i + 1]) - ord(s[i]))
		return find


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		s = list(s)
		i = 0
		j = len(s) - 1
		a = 0
		cnt = 0
		c = 0
		d = 0
		while i < j:
			if s[i] != '?' and s[j] != '?':
				if s[i] != s[j]:
					return -1
			if s[i] != '?' and s[j] == '?':
				s[j] = s[i]
			if s[i] == '?' and s[j] != '?':
				s[i] = s[j]
			i = i + 1
			j = j - 1
		for i in range(len(s)):
			if s[i] != '?':
				item = s[i]
				d = i
				break
		for i in range(d + 1, len(s)):
			if s[i] != '?':
				c = c + abs(ord(item) - ord(s[i]))
				item = s[i]
		return c


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		mid = int(math.ceil(len(s) / 2))
		last_char = None
		min_sum = 0
		for i in range(mid):
			left = s[i]
			right = s[len(s) - 1 - i]
			if left == '?':
				left = right
			if right == '?':
				right = left
			if left != right:
				return -1
			if left == '?':
				continue
			if last_char is not None:
				min_sum += int(abs(ord(left) - ord(last_char)))
			last_char = left
		return min_sum * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		n = len(s)
		s = list(s)
		for i in range(n // 2):
			if s[i] != s[n - i - 1]:
				if s[i] == '?':
					s[i] = s[n - i - 1]
				elif s[n - i - 1] == '?':
					s[n - i - 1] = s[i]
				else:
					return -1
		ans = 0
		p = '?'
		for i in range(n):
			if s[i] == '?':
				continue
			if p == '?':
				p = s[i]
			ans += abs(ord(s[i]) - ord(p))
			p = s[i]
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		nearest = lambda x: x
		n = len(s)
		lis = list(s)
		for i in range(n // 2):
			if lis[i] != lis[n - i - 1]:
				if lis[i] == '?':
					lis[i] = lis[n - i - 1]
				elif lis[n - i - 1] == '?':
					lis[n - i - 1] = lis[i]
				else:
					return -1
		i = 0
		while i < n // 2:
			cur = lis[i]
			beg = i
			if cur == '?':
				prev = lis[i - 1] if i > 0 else None
				while i < n // 2 and lis[i] == cur:
					i += 1
				nex = lis[i]
				if prev:
					lis[beg:i] = [nearest(prev)] * (i - beg)
				else:
					lis[beg:i] = [nearest(nex)] * (i - beg)
			else:
				i += 1
		for i in range(n // 2):
			if lis[i] != lis[n - i - 1]:
				if lis[i] == '?':
					lis[i] = lis[n - i - 1]
				elif lis[n - i - 1] == '?':
					lis[n - i - 1] = lis[i]
		res = 0
		for i in range(1, n):
			res += abs(ord(lis[i]) - ord(lis[i - 1]))
		return res


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		i = 0
		j = len(s) - 1
		c = None
		while i <= j:
			if s[i] == '?' and s[j] == '?':
				i += 1
				j -= 1
				continue
			if s[i] != s[j] and '?' not in (s[i], s[j]):
				return -1
			c = s[i] if s[i] != '?' else s[j]
			break
		if c is None:
			return 0
		i = 0
		j = len(s) - 1
		s = list(s)
		while i <= j:
			if s[i] != s[j] and '?' not in (s[i], s[j]):
				return -1
			if s[i] == '?' and s[j] == '?':
				if i == 0:
					s[i] = c
					s[j] = c
				else:
					s[i] = s[i - 1]
					s[j] = s[j + 1]
			elif s[i] == '?':
				s[i] = s[j]
			else:
				s[j] = s[i]
			i += 1
			j -= 1
		_sum = 0
		for i in range(1, len(s)):
			_sum += abs(ord(s[i]) - ord(s[i - 1]))
		return _sum


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		(i, j) = (0, len(s) - 1)
		cur = None
		ans = 0
		while i <= j:
			if s[i] == '?' and s[j] == '?':
				i += 1
				j -= 1
				continue
			if s[i] == '?':
				if not cur:
					cur = s[j]
				else:
					ans += 2 * abs(ord(cur) - ord(s[j]))
					cur = s[j]
			elif s[j] == '?':
				if not cur:
					cur = s[i]
				else:
					ans += 2 * abs(ord(cur) - ord(s[i]))
					cur = s[i]
			else:
				if s[i] != s[j]:
					return -1
				if not cur:
					cur = s[i]
				else:
					ans += 2 * abs(ord(cur) - ord(s[i]))
					cur = s[i]
			i += 1
			j -= 1
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:

		def get(l, h):
			while l <= h:
				if a[l] != '?' and a[h] != '?':
					if a[l] != a[h]:
						return -1
					else:
						return a[l]
				elif a[l] != '?' or a[h] != '?':
					return a[l] if a[l] != '?' else a[h]
				l += 1
				h -= 1
			return 0
		a = list(s)
		l = 0
		h = len(a) - 1
		while l < h:
			if a[l] != '?' and a[h] != '?':
				if a[l] != a[h]:
					return -1
				else:
					l += 1
					h -= 1
			elif a[l] != '?' and a[h] == '?':
				a[h] = a[l]
				l += 1
				h -= 1
			elif a[l] == '?' and a[h] != '?':
				a[l] = a[h]
				l += 1
				h -= 1
			elif l == 0 and h == len(a) - 1:
				x = get(l, h)
				if x == -1 or x == 0:
					return x
				else:
					a[l] = x
					a[h] = x
					l += 1
					h -= 1
			else:
				a[l] = a[l - 1]
				a[h] = a[h + 1]
				l += 1
				h -= 1
		ans = 0
		for i in range(len(a) - 1):
			ans += abs(ord(a[i]) - ord(a[i + 1]))
		return ans


class Solution:

	def minimumSum(self, s: str) -> int:

		def possible(s):
			(low, high) = (0, len(s) - 1)
			while low < high:
				if s[low] != '?' and s[high] != '?' and (s[low] != s[high]):
					return False
				low += 1
				high -= 1
			return True

		def solve(st):
			s = list(st)
			i = 0
			(low, high) = (0, len(s) - 1)
			while low < high:
				if s[low] == '?':
					s[low] = s[high]
				elif s[high] == '?':
					s[high] = s[low]
				low += 1
				high -= 1
			while i < len(s) and s[i] == '?':
				i += 1
			if i == len(s):
				return 0
			ans = 0
			prev = s[i]
			for x in range(i, len(s)):
				if s[x] == '?':
					s[x] = prev
				ans += abs(ord(s[x]) - ord(prev))
				prev = s[x]
			return ans
		if not possible(s):
			return -1
		else:
			return solve(s)


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		last = 0
		i = 0
		j = len(s) - 1
		ans = 0
		while i <= j:
			if s[i] != '?' and s[j] != '?' and (s[i] != s[j]):
				return -1
			if s[i] == s[j] == '?':
				pass
			elif s[i] == s[j] or s[i] == '?' or s[j] == '?':
				cur = s[i] if s[i] != '?' else s[j]
				if last != 0:
					ans += 2 * abs(ord(cur) - ord(last))
				last = cur
			i += 1
			j -= 1
		return ans


import math

class Solution:

	def asciisum(self, s, n):
		(summ, n) = (0, n)
		for i in range(1, n):
			summ += abs(ord(s[i]) - ord(s[i - 1]))
		return summ

	def minimumSum(self, s: str) -> int:
		n = len(s)
		s = list(s)
		(start, end) = (0, n - 1)
		while start < end:
			if s[start] != '?' and s[end] != '?':
				if s[start] != s[end]:
					return -1
			elif s[start] == '?' and s[end] == '?':
				if start > 0:
					(s[start], s[end]) = (s[start - 1], s[start - 1])
				else:
					(ele, idx, idx2) = ('', 1, n - 2)
					while idx < idx2:
						if s[idx] != '?':
							ele = s[idx]
							break
						elif s[idx2] != '?':
							ele = s[idx2]
							break
						idx += 1
						idx2 -= 1
					if ele:
						(s[start], s[end]) = (ele, ele)
					else:
						(s[start], s[end]) = ('a', 'a')
			elif s[start] == '?':
				s[start] = s[end]
			else:
				s[end] = s[start]
			start += 1
			end -= 1
		return self.asciisum(s, n)


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		ans = 0
		start = 0
		end = len(s) - 1
		for i in range(end + 1):
			if s[i] != '?':
				prev = s[i]
				break
			if s[end - i] != '?':
				prev = s[end - i]
				break
		while start <= end:
			if s[start] == '?' and s[end] == '?':
				start += 1
				end -= 1
			elif s[start] != '?' and s[end] != '?':
				if s[start] != s[end]:
					return -1
				else:
					ans += abs(ord(prev) - ord(s[start]))
				prev = s[start]
				start += 1
				end -= 1
			else:
				if s[start] != '?':
					temp = s[start]
				if s[end] != '?':
					temp = s[end]
				start += 1
				end -= 1
				ans += abs(ord(temp) - ord(prev))
				prev = temp
		return ans * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		l = 0
		h = len(s) - 1
		s = list(s)
		while l < h:
			if s[l] != s[h]:
				if s[l] == '?':
					s[l] = s[h]
				elif s[h] == '?':
					s[h] = s[l]
				else:
					return -1
			l += 1
			h -= 1
		ans = 0
		c = '?'
		for i in range(len(s)):
			if s[i] != '?':
				if c == '?':
					c = s[i]
				else:
					ans += abs(ord(s[i]) - ord(c))
					c = s[i]
		return ans


class Solution:

	def minimumSum(self, s: str) -> int:
		for i in range(len(s) // 2):
			j = len(s) - 1 - i
			if s[i] == s[j] or s[i] == '?' or s[j] == '?':
				if s[i] != '?':
					s = s[:j] + s[i] + s[j + 1:]
				elif s[j] != '?':
					s = s[:i] + s[j] + s[i + 1:]
				else:
					continue
			else:
				return -1
		sum = 0
		i = 0
		while i < len(s) // 2:
			c = s[i]
			if c == '?':
				while s[i] == '?' and i < len(s) // 2:
					i += 1
			else:
				i += 1
				while s[i] == '?' and i < len(s) // 2:
					i += 1
				if s[i] != '?':
					sum += abs(ord(c) - ord(s[i]))
		return sum * 2


class Solution:

	@staticmethod
	def minimumSum(s: str) -> int:
		l = len(s)
		sb = list(s)
		for i in range(l // 2):
			if s[i] == '?' and s[l - 1 - i] == '?':
				continue
			elif s[i] == '?' and s[l - 1 - i] != '?':
				sb[i] = s[l - 1 - i]
			elif s[i] != '?' and s[l - 1 - i] == '?':
				sb[l - 1 - i] = s[i]
			elif s[i] != s[l - 1 - i]:
				return -1
		count = 0
		prev = ' '
		for i in range(l):
			curr = sb[i]
			if curr == '?':
				continue
			if prev == ' ':
				prev = curr
				continue
			count += abs(ord(curr) - ord(prev))
			prev = curr
		return count


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		ans = 0
		n = len(s)
		(l, h) = (0, n - 1)
		while l <= h:
			if s[l] != '?' and s[h] != '?' and (s[l] != s[h]):
				return -1
			l += 1
			h -= 1
		s = [x for x in s]
		(l, h) = (0, n - 1)
		while l < h:
			if s[l] != s[h]:
				if s[l] != '?':
					s[h] = s[l]
				else:
					s[l] = s[h]
			l += 1
			h -= 1
		i = 0
		prevchar = ''
		while i <= (n + 1) // 2:
			if s[i] != '?' and prevchar != '':
				ans += abs(ord(s[i]) - ord(prevchar))
			if s[i] != '?':
				prevchar = s[i]
			i += 1
		return ans * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		n = len(s)
		cur = '?'
		ans = 0
		for i in range(n // 2):
			if s[i] != '?' and s[n - i - 1] != '?' and (s[i] != s[n - i - 1]):
				return -1
			if s[i] == '?' and s[n - i - 1] != '?':
				if cur == '?':
					cur = s[n - i - 1]
				else:
					ans += abs(ord(s[n - i - 1]) - ord(cur))
					cur = s[n - i - 1]
			if s[i] != '?':
				if cur == '?':
					cur = s[i]
				else:
					ans += abs(ord(s[i]) - ord(cur))
					cur = s[i]
		return ans * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		left = 0
		right = len(s) - 1
		item = ''
		while left <= right:
			if s[left] != '?':
				item = s[left]
				break
			if s[right] != '?':
				item = s[right]
				break
			left += 1
			right -= 1
		left = 0
		right = len(s) - 1
		ans = 0
		a = ''
		while left < right:
			if s[left] != '?' and s[right] != '?':
				if s[left] != s[right]:
					return -1
				else:
					ans += abs(ord(item) - ord(s[left]))
					item = s[left]
					a += item
			elif s[left] == '?' and s[right] == '?':
				left += 1
				right -= 1
				a += item
				continue
			elif s[left] == '?':
				a += item
				ans += abs(ord(item) - ord(s[right]))
				item = s[right]
			elif s[right] == '?':
				a += item
				ans += abs(ord(item) - ord(s[left]))
				item = s[left]
			left += 1
			right -= 1
		if left == right:
			ans += abs(ord(item) - ord(s[right]))
		return ans * 2


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		a = list(s)
		p = a[0]
		for i in range(len(s)):
			if s[i] != '?' and s[len(s) - i - 1] != '?' and (s[i] != s[len(s) - i - 1]):
				return -1
			elif a[i] != '?':
				a[len(a) - i - 1] = a[i]
				p = ord(a[i]) - 97
			elif a[len(a) - i - 1] != '?':
				a[i] = a[len(a) - i - 1]
				p = ord(a[i]) - 97
		ans = 0
		for i in range(len(a)):
			if a[i] == '?':
				continue
			else:
				ans += abs(p - ord(a[i]) + 97)
				p = ord(a[i]) - 97
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		prev = '?'
		count = 0
		if len(s) < 2:
			return 0
		if len(s) % 2 == 1:
			firstHalf = s[:len(s) // 2]
			secondHalf = s[len(s) // 2 + 1:][::-1]
			mid = True
		else:
			firstHalf = s[:len(s) // 2]
			secondHalf = s[len(s) // 2:][::-1]
			mid = False
		for i in range(len(firstHalf)):
			(f, s) = (firstHalf[i], secondHalf[i])
			if f != s and (f != '?' and s != '?'):
				return -1
			elif f != s:
				if f == '?':
					firstHalf = firstHalf[:i] + s + firstHalf[i + 1:]
					prev = s
				else:
					secondHalf = secondHalf[:i] + f + secondHalf[i + 1:]
					prev = f
			elif f == '?' and s == '?':
				if prev != '?':
					firstHalf = firstHalf[:i] + prev + firstHalf[i + 1:]
					secondHalf = secondHalf[:i] + prev + secondHalf[i + 1:]
				else:
					count += 1
			else:
				prev = f
			if count != 0 and prev != '?':
				firstHalf = prev * count + firstHalf[count:]
				secondHalf = prev * count + secondHalf[count:]
				count = 0
		s = firstHalf + s[len(s) // 2] + secondHalf[::-1] if mid else firstHalf + secondHalf[::-1]
		if mid and s[len(s) // 2] == '?':
			s = firstHalf + prev + secondHalf[::-1]
		if '?' in s:
			return 0
		else:
			sumSoFar = 0
			for i in range(1, len(s)):
				sumSoFar += abs(ord(s[i]) - ord(s[i - 1]))
		return sumSoFar


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		n = len(s)
		s = list(s)
		if n == 1:
			return 0
		left = 0
		right = len(s) - 1
		prev = '#'
		ans = 0
		while left <= right:
			if s[left] == '?' and s[right] == '?':
				left += 1
				right -= 1
				continue
			elif s[left] == '?':
				if prev != '#':
					ans += 2 * abs(ord(prev) - ord(s[right]))
				s[left] = s[right]
				prev = s[left]
			elif s[right] == '?':
				if prev != '#':
					ans += 2 * abs(ord(prev) - ord(s[left]))
				s[right] = s[left]
				prev = s[right]
			elif s[left] == s[right]:
				if prev != '#':
					ans += 2 * abs(ord(prev) - ord(s[right]))
				prev = s[left]
			else:
				return -1
			left += 1
			right -= 1
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		s = list(s)
		left = 0
		right = len(s) - 1
		for i in range(len(s) // 2):
			if s[i] != '?':
				last = s[i]
				break
			if s[len(s) - i - 1] != '?':
				last = s[len(s) - i - 1]
				break
			elif i == len(s) // 2 - 1:
				return 0
		ans = 0
		while left < right:
			if s[left] == s[right] == '?':
				s[left] = s[right] = last
			elif s[left] == '?':
				s[left] = s[right]
				last = s[left]
			elif s[right] == '?':
				s[right] = s[left]
				last = s[left]
			elif s[left] != s[right]:
				return -1
			else:
				last = s[left]
			left += 1
			right -= 1
		for i in range(1, len(s)):
			ans += abs(ord(s[i]) - ord(s[i - 1]))
		return ans


import math

class Solution:

	def minimumSum(self, s: str) -> int:
		arr = [i for i in s]
		(start, end) = (0, len(arr) - 1)
		prev = curr = arr[0]
		ans = 0
		while start < end:
			if arr[start] == arr[end]:
				if arr[start] == '?':
					pass
			elif arr[start] == '?' or arr[end] == '?':
				if arr[start] == '?':
					arr[start] = arr[end]
				else:
					arr[end] = arr[start]
			else:
				return -1
			start += 1
			end += -1
		for i in range(len(arr) // 2 + 1):
			if arr[i] != '?':
				prev = curr
				curr = arr[i]
				if prev != '?':
					ans += abs(ord(prev) - ord(curr))
		return ans * 2