Given two strings s1 and s2, The task is to convert s1 into a palindrome such that s1 contain s2 as a substring in a minimum number of operation.
In a single operation, we can replace any word of s1 with any character.
Note: If it is not possible to convert s1 such that it is a palindrome as well as contains substring of s2, then return -1.
Example 1:
Input:
s1="abaa" s2="bb"
Output: 1
Explanation:
we can replace s1[2]='a' with 'b'.
So the new s1 will be like "abba",
having s2 as a substring.
Example 2:
Input:
s1="abbd" s2="mr"
Output: 4
Explanation:
1st: s1="mrbd" --> 2 operations (this is the 
minimum operation to make s2 a substring of s1) 
2nd: s1="mrrm" --> 2 operations 
(this is the minimum operation to make s1 palindrome)
Your Task:  
You don't need to read input or print anything. Complete the function specialPalindrome() which takes the two strings s1 and s2 as input parameters. Return the minimum number of operations needs to convert s1 such that it is a palindrome and having s2 as a substring in s1.
Expected Time Complexity: O(N*M) [N: size of s1 and M: size of s2]
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ |s2| ≤ |s1| ≤  1000

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M) [N: size of s1 and M: size of s2]
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution():

    def specialPalindrome(self,s1, s2):

        #your code goes here

Solutions:
class Solution:

	def specialPalindrome(self, s1, s2):

		def _get(k):
			return (s2[k - i], True) if i <= k < i + N2 else (s1[k], False)
		INV = 1000000000
		N1 = len(s1)
		N2 = len(s2)
		ans = INV
		baseline = 0
		for i in range(N1 // 2):
			if s1[i] != s1[N1 - 1 - i]:
				baseline += 1
		for i in range(N1 - N2 + 1):
			tmp = baseline
			for j in range(i, i + N2):
				(c0, (c1, f1)) = (s2[j - i], _get(N1 - 1 - j))
				if s1[j] != s1[N1 - 1 - j] and (not f1 or j < N1 - 1 - j):
					tmp -= 1
				if c0 != s1[j]:
					tmp += 1
				if c0 != c1:
					if f1:
						tmp = INV
						break
					tmp += 1
			ans = min(ans, tmp)
		return -1 if ans >= INV else ans


class Solution:

	def specialPalindrome(self, s1, s2):
		ret = float('inf')
		m = len(s1)
		n = len(s2)
		for i in range(m - n + 1):
			s3 = list(s1[:i]) + list(s2) + list(s1[i + n:])
			t = [1] * i + [0] * n + [1] * (m - i - n)
			tmp = 0
			for j in range(n):
				if s1[i + j] != s2[j]:
					tmp += 1
			j = 0
			k = m - 1
			while j < k:
				if s3[j] != s3[k]:
					if t[j] == 1 or t[k] == 1:
						tmp += 1
					else:
						tmp = float('inf')
						break
				j += 1
				k -= 1
			ret = min(ret, tmp)
		return ret if ret != float('inf') else -1


class Solution:

	def solver(S, L, R):
		steps = 0
		for i in range(len(S) // 2):
			if i >= L and len(S) - 1 - i <= R and (S[i] != S[len(S) - 1 - i]):
				return -1
			if S[i] != S[len(S) - 1 - i]:
				steps += 1
		return steps

	def specialPalindrome(ignore, s1, s2):
		(a, b) = (len(s1), len(s2))
		if b > a:
			return -1
		cost = 10000
		for i in range(a - b + 1):
			localcost = 0
			for j in range(b):
				if s1[i + j] != s2[j]:
					localcost += 1
			s3 = s1[0:i] + s2 + s1[i + b:]
			palincost = Solution.solver(s3, i, i + b - 1)
			if palincost != -1:
				localcost += palincost
				cost = min(cost, localcost)
		return -1 if cost == 10000 else cost


import math
INF = float('inf')

class Solution:

	def specialPalindrome(self, s1, s2):
		l1 = len(s1)
		l2 = len(s2)
		ans = INF
		for i in range(l1 - l2 + 1):
			temp = s1[:i] + s2 + s1[i + l2:]
			cost = 0
			for j in range(i, i + l2):
				if s1[j] != temp[j]:
					cost += 1
			z = 0
			for j in range(math.ceil(l1 / 2)):
				if (j < i or j >= i + l2) and temp[j] != temp[l1 - j - 1]:
					cost += 1
				elif temp[j] != temp[l1 - j - 1] and (l1 - j - 1 < i or l1 - j - 1 >= i + l2):
					cost += 1
				elif temp[j] != temp[l1 - j - 1]:
					z = 1
					break
			if z == 0:
				ans = min(ans, cost)
		if ans == INF:
			return -1
		return ans


class Solution:

	def specialPalindrome(self, s1, s2):
		(N, M) = (len(s1), len(s2))
		if N < M:
			return -1
		res = -1
		for i in range(N - M + 1):
			tmp = s1[:i] + s2 + s1[i + M:]
			cost = 0
			for j in range(i, i + M):
				if tmp[j] != s1[j]:
					cost += 1
			f = True
			for j in range((N + 1) // 2):
				if (j < i or j >= i + M) and tmp[j] != tmp[N - j - 1]:
					cost += 1
				elif (N - i - 1 < j or N - M - i - 1 >= j) and tmp[j] != tmp[N - j - 1]:
					cost += 1
				elif tmp[j] != tmp[N - j - 1]:
					f = False
					break
			if f:
				res = cost if res == -1 else min(res, cost)
		return res


class Solution:

	def specialPalindrome(self, s1, s2):

		def get(k):
			return (s2[k - i], True) if i <= k < i + N2 else (s1[k], False)
		(Inv, N1, N2) = (10 ** 9, len(s1), len(s2))
		(ans, baseline) = (Inv, 0)
		for i in range(N1 // 2):
			if s1[i] != s1[N1 - 1 - i]:
				baseline += 1
		for i in range(N1 - N2 + 1):
			tmp = baseline
			for j in range(i, i + N2):
				(c0, (c1, f1)) = (s2[j - i], get(N1 - 1 - j))
				if s1[j] != s1[N1 - 1 - j] and (not f1 or j < N1 - 1 - j):
					tmp -= 1
				if c0 != s1[j]:
					tmp += 1
				if c0 != c1:
					if f1:
						tmp = Inv
						break
					tmp += 1
			ans = min(ans, tmp)
		return -1 if ans >= Inv else ans


class Solution:

	def specialPalindrome(self, s1, s2):
		s1l = len(s1)
		s2l = len(s2)
		ans = float('inf')
		if s1l < s2l:
			return -1
		for i in range(s1l - s2l + 1):
			temp = s1[:i] + s2 + s1[i + s2l:]
			cost = 0
			for j in range(i, i + s2l):
				if temp[j] != s1[j]:
					cost += 1
			flag = True
			for j in range(s1l // 2):
				if (i > j or j >= i + s2l) and temp[j] != temp[s1l - j - 1]:
					cost += 1
				elif (s1l - i - s2l - 1 >= j or s1l - i - 1 < j) and temp[j] != temp[s1l - j - 1]:
					cost += 1
				elif temp[j] != temp[s1l - j - 1]:
					flag = False
					break
			if flag == True:
				ans = min(ans, cost)
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def solve(self, temp, x, y):
		c = 0
		(i, j) = (0, len(temp) - 1)
		while i < j:
			if temp[i] != temp[j]:
				c += 1
				if i >= x and j <= y:
					return 1000000000.0
			i += 1
			j -= 1
		return c

	def specialPalindrome(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		mini = 1000000000.0
		if n > (m + 1) // 2:
			return -1
		for i in range(m - n + 1):
			c = 0
			for j in range(n):
				if s1[i + j] != s2[j]:
					c += 1
			temp = s1[0:i] + s2 + s1[i + n:]
			c += self.solve(temp, i, i + n - 1)
			mini = min(mini, c)
		return mini


class Solution:

	def makePalindrome(self, arr, i, m):
		start = 0
		end = len(arr) - 1
		count = 0
		while start < end:
			if arr[start] != arr[end]:
				if start >= i and end <= i + m - 1:
					return 1000000000.0
				else:
					count += 1
			start += 1
			end -= 1
		return count

	def specialPalindrome(self, s1, s2):
		mini = 1000000000.0
		(m, n) = (len(s1), len(s2))
		if m < n:
			return -1
		for i in range(0, m - n + 1):
			count = 0
			temp = list(s1)
			for j in range(n):
				if s1[i + j] != s2[j]:
					count += 1
					temp[i + j] = s2[j]
			palin = self.makePalindrome(temp, i, n)
			total = count + palin
			mini = min(mini, total)
		return -1 if mini == 1000000000.0 else mini


class Solution:

	def specialPalindrome(sefl, s1, s2):
		costs = []
		for i in range(0, len(s1) - len(s2) + 1):
			s3 = s1[0:i] + s2 + s1[i + len(s2):]
			cost = 0
			for j in range(i, i + len(s2)):
				if s1[j] != s3[j]:
					cost += 1
			pcost = 0
			for k in range(0, len(s3) // 2):
				if s3[k] != s3[-(k + 1)]:
					if i <= k <= i + len(s2) and i <= len(s3) - k <= i + len(s2):
						pcost = -1
						break
					elif i <= k <= i + len(s2):
						pcost += 1
					elif i <= len(s1) - k <= i + len(s2):
						pcost += 1
					else:
						pcost += 1
			if pcost >= 0:
				costs.append(cost + pcost)
		min_cost = sorted(costs)[0] if costs else -1
		return min_cost


class Solution:

	def specialPalindrome(self, s1, s2):
		makeP = 0
		(i, j) = (0, len(s1) - 1)
		dic = {}
		while i <= j:
			if s1[i] != s1[j]:
				makeP += 1
				dic[i] = s1[i]
				dic[j] = s1[j]
			i += 1
			j -= 1

		def check(string, i, pat):
			score = 0
			aldy = {}
			j = 0
			while j < len(pat):
				if i in aldy:
					if pat[j] != aldy[i]:
						return (False, 0)
				elif i not in dic:
					aldy[i] = pat[j]
					aldy[len(s1) - i - 1] = pat[j]
					if string[i] != pat[j]:
						if i != len(s1) - i - 1:
							score += 2
						else:
							score += 1
				else:
					c1 = string[i]
					c2 = string[len(s1) - i - 1]
					if pat[j] != c1 and pat[j] != c2:
						score += 1
					aldy[i] = pat[j]
					aldy[len(s1) - i - 1] = pat[j]
				i += 1
				j += 1
			return (True, score)
		minimum = float('inf')
		for i in range(len(s1) - len(s2) + 1):
			(isposs, s) = check(s1, i, s2)
			if isposs:
				minimum = min(minimum, s)
		ans = makeP + minimum
		return ans if ans != float('inf') else -1


class Solution:

	def specialPalindrome(self, s1, s2):
		if len(s2) > len(s1):
			return -1
		if s2 in s1:
			count = 0
			for j in range(0, l1 // 2):
				if s1[j] != s1[l1 - 1 - j]:
					count += 1
			return count
		else:
			l2 = len(s2)
			l1 = len(s1)
			l2_poli = True
			for j in range(0, l2 // 2):
				if s2[j] != s2[l2 - 1 - j]:
					l2_poli = False
					break
			ans = -1
			for i in range(len(s1) + 1 - len(s2)):
				count = l2 - sum((x == y for (x, y) in zip(s1[i:i + len(s2)], s2)))
				s1_temp = s1[:i] + s2 + s1[i + len(s2):]
				for j in range(0, l1 // 2):
					if s1_temp[j] != s1_temp[l1 - 1 - j]:
						if j >= i and l1 - 1 - j <= i + len(s2) - 1:
							count = -1
							break
						count += 1
				if ans != -1:
					ans = min(ans, count if count != -1 else ans)
				else:
					ans = count if count != -1 else -1
			return ans


import sys

def f(a, b, strt, end):
	ans = 0
	i = 0
	j = len(a) - 1
	while i <= j:
		if i >= strt and i <= end:
			if j >= strt and j <= end:
				if b[i - strt] != b[j - strt]:
					return -1
				if a[i] != b[i - strt]:
					ans += 1
				if a[j] != b[j - strt] and i != j:
					ans += 1
			else:
				if a[i] != b[i - strt]:
					ans += 1
				if b[i - strt] != a[j] and i != j:
					ans += 1
		elif j >= strt and j <= end:
			if a[j] != b[j - strt]:
				ans += 1
			if b[j - strt] != a[i] and i != j:
				ans += 1
		elif a[i] != a[j]:
			ans += 1
		i += 1
		j -= 1
	return ans

class Solution:

	def specialPalindrome(self, s1, s2):
		ans = sys.maxsize
		for i in range(0, len(s1) - len(s2) + 1):
			val = f(s1, s2, i, i + len(s2) - 1)
			if val != -1:
				ans = min(ans, val)
		if ans == sys.maxsize:
			ans = -1
		return ans


class Solution:

	def specialPalindrome(self, s1, s2):
		(n, m) = (len(s1), len(s2))
		org = list(s1)
		slis = org[:]
		res = 100000000.0
		for i in range(n - m + 1):
			cur = 0
			for j in range(m):
				if slis[i + j] != s2[j]:
					slis[i + j] = s2[j]
					cur += 1
			cr = range(i, i + m)
			for x in range(n // 2):
				if slis[x] != slis[n - x - 1]:
					if x in cr and n - x - 1 in cr:
						break
					else:
						cur += 1
			else:
				res = min(res, cur)
			slis = org[:]
		return res if res < 100000000.0 else -1


class Solution:

	def specialPalindrome(self, s1, s2):
		(n1, n2) = (len(s1), len(s2))
		ans = float('inf')
		for i in range(n1 - n2 + 1):
			costs = 0
			for k in range(n2):
				if s1[i + k] != s2[k]:
					costs += 1
			(j1, j2) = (0, n1 - 1)
			while j1 < j2:
				if i <= j1 < i + n2 and i <= j2 < i + n2 and (s2[j1 - i] != s2[j2 - i]):
					break
				left = s1[j1]
				if i <= j1 < i + n2:
					left = s2[j1 - i]
				right = s1[j2]
				if i <= j2 < i + n2:
					right = s2[j2 - i]
				if left != right:
					costs += 1
				j1 += 1
				j2 -= 1
			else:
				ans = min(ans, costs)
		return -1 if ans == float('inf') else ans


class Solution:

	def palindrome(self, a, b, st, end):
		i = 0
		j = len(a) - 1
		i2 = 0
		j2 = len(b) - 1
		op = 0
		while i < j:
			if i < st and j > end or j < st or i > end:
				if a[i] != a[j]:
					op += 1
			elif j > end:
				if b[i2] != a[j]:
					op += 1
				i2 += 1
			elif i < st:
				if a[i] != b[j2]:
					op += 1
				j2 -= 1
			else:
				if b[i2] != b[j2]:
					return 99999
				i2 += 1
				j2 -= 1
			i += 1
			j -= 1
		return op

	def specialPalindrome(self, a, b):
		ans = 99999
		for i in range(len(a) - len(b) + 1):
			st = i
			end = i + len(b) - 1
			temp = 0
			k = 0
			for j in range(st, end + 1):
				if a[j] != b[k]:
					temp += 1
				k += 1
			t = self.palindrome(a, b, st, end)
			if t == ans:
				temp = t
			else:
				temp += t
			ans = min(ans, temp)
		if ans == 99999:
			return -1
		return ans


class Solution:

	def specialPalindrome(self, s, t):

		def makePalindrome(s, l, h):
			(i, j) = (0, len(s) - 1)
			cnt = 0
			while i < j:
				if i >= l and i <= h and (j <= h) and (j >= l) and (s[i] != s[j]):
					return float('inf')
				if s[i] != s[j]:
					cnt += 1
				i += 1
				j -= 1
			return cnt
		mini = float('inf')
		(n, m) = (len(s), len(t))
		for i in range(0, n - m + 1):
			temp = s[:i] + t + s[i + m:]
			cnt = 0
			for j in range(m):
				if s[i + j] != t[j]:
					cnt += 1
			mini = min(mini, makePalindrome(temp, i, i + m - 1) + cnt)
		return -1 if mini == float('inf') else mini


class Solution:

	def specialPalindrome(self, s1, s2):
		l1 = len(s1)
		l2 = len(s2)
		if l1 == l2 and s1 != s2:
			return -1
		f = 1
		m = 10 ** 20
		for i in range(l1 - l2 + 1):
			f = 1
			c = 0
			s3 = s1[:i] + s2 + s1[i + l2:]
			for k in range(i, i + l2):
				if s1[k] != s3[k]:
					c += 1
			for j in range(l1 // 2):
				if (j < i or j >= i + l2) and s3[j] != s3[l1 - j - 1]:
					c += 1
				elif j >= i and l1 - j - 1 >= i + l2 and (s3[j] != s3[l1 - j - 1]):
					c += 1
				elif j >= i and l1 - j - 1 < i + l2 and (s3[j] != s3[l1 - j - 1]):
					f = 0
					break
			if f != 0:
				m = min(c, m)
		if m == 10 ** 20:
			return -1
		return m


class Solution:

	def specialPalindrome(self, s1, s2):
		if len(s2) > len(s1):
			return -1
		mini = -1
		for i in range(len(s1) - len(s2) + 1):
			(st, end) = (i, i + len(s2) - 1)
			(m, n) = (0, len(s1) - 1)
			tmp = 0
			stop = False
			while n >= m:
				(c1, c2) = (None, None)
				(b1, b2) = (False, False)
				if m == n:
					if st <= m <= end:
						c = s2[m - st]
						if c != s1[m]:
							tmp += 1
				else:
					if st <= m <= end:
						c1 = s2[m - st]
						b1 = True
						if c1 != s1[m]:
							tmp += 1
					else:
						c1 = s1[m]
					if st <= n <= end:
						c2 = s2[n - st]
						b2 = True
						if c2 != s1[n]:
							tmp += 1
					else:
						c2 = s1[n]
					if b1 and b2 and (c1 != c2):
						stop = True
						break
					if c1 != c2:
						tmp += 1
				m += 1
				n -= 1
			if not stop:
				if mini == -1:
					mini = tmp
				else:
					mini = min(mini, tmp)
		return mini


class Solution:

	def specialPalindrome(self, s1, s2):
		a = 1
		for _ in range(1000):
			a += 1
		s1 = [c for c in s1]
		s2 = [c for c in s2]
		ans = float('inf')
		for i in range(0, len(s1) - len(s2) + 1):
			s = s1[:]
			count = 0
			for j in range(len(s2)):
				if s1[i + j] != s2[j]:
					s[i + j] = s2[j]
					count += 1
			left = 0
			right = len(s1) - 1
			f = True
			while left < right:
				if s[left] != s[right]:
					if i <= left < i + len(s2) and i <= right < i + len(s2):
						f = False
						break
					count += 1
				left += 1
				right -= 1
			if f:
				ans = min(ans, count)
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def specialPalindrome(self, s1, s2):
		a = list(s1)
		b = list(s2)
		l1 = len(s1)
		l2 = len(s2)
		ans = float('inf')
		for i in range(l1 - l2 + 1):
			temp = list(a[:i] + b + a[i + l2:])
			cost = 0
			for j in range(i, i + l2):
				if s1[j] != temp[j]:
					cost += 1
			z = 0
			for j in range(int(l1 / 2)):
				if (j < i or j >= i + l2) and temp[j] != temp[l1 - j - 1]:
					cost += 1
				elif temp[j] != temp[l1 - j - 1] and (l1 - j - 1 < i or l1 - j - 1 >= i + l2):
					cost += 1
				elif temp[j] != temp[l1 - j - 1]:
					z = 1
					break
			if z == 0:
				ans = min(ans, cost)
		return int(ans) if ans != float('inf') else -1


class Solution:

	def specialPalindrome(self, s1, s2):
		s1 = list(s1)
		s2 = list(s2)
		n = len(s1)
		m = len(s2)
		ans = n + 1
		for i in range(n - m + 1):
			s = s1.copy()
			for j in range(i, i + m):
				s[j] = s2[j - i]
			pos = True
			for j in range(n):
				if s[j] != s[n - j - 1]:
					if j >= i and j < i + m and (n - j - 1 >= i) and (n - j - 1 < i + m):
						pos = False
						break
					if j >= i and j < i + m:
						s[n - j - 1] = s[j]
					else:
						s[j] = s[n - j - 1]
			if not pos:
				continue
			cnt = 0
			for i in range(n):
				if s[i] != s1[i]:
					cnt += 1
			ans = min(ans, cnt)
		return -1 if ans == n + 1 else ans


import sys

def calculate(a, b, beg, end):
	sol = 0
	i = 0
	j = len(a) - 1
	while i <= j:
		if i >= beg and i <= end:
			if j >= beg and j <= end:
				if b[i - beg] != b[j - beg]:
					return -1
				if a[i] != b[i - beg]:
					sol += 1
				if a[j] != b[j - beg] and i != j:
					sol += 1
			else:
				if a[i] != b[i - beg]:
					sol += 1
				if b[i - beg] != a[j] and i != j:
					sol += 1
		elif j >= beg and j <= end:
			if a[j] != b[j - beg]:
				sol += 1
			if b[j - beg] != a[i] and i != j:
				sol += 1
		elif a[i] != a[j]:
			sol += 1
		i += 1
		j -= 1
	return sol

class Solution:

	def specialPalindrome(self, s1, s2):
		sol = sys.maxsize
		for i in range(0, len(s1) - len(s2) + 1):
			val = calculate(s1, s2, i, i + len(s2) - 1)
			if val != -1:
				sol = min(sol, val)
		if sol == sys.maxsize:
			sol = -1
		return sol


class Solution:

	def specialPalindrome(self, s1, s2):
		mud = 0
		menor = 1000
		a = 0
		for i in range(len(s1) - len(s2) + 1):
			s3 = s1[:i] + s2 + s1[i + len(s2):]
			for y in range(i, i + len(s2)):
				k = len(s3) - 1 - y
				if s3[y] != s3[k] and k >= i and (k < len(s2) + i):
					a = 1
					break
				if s3[y] != s1[y]:
					mud += 1
			if a == 0:
				for p in range(len(s3) // 2):
					if s3[p] != s3[len(s3) - p - 1]:
						mud += 1
				if mud < menor:
					menor = mud
			mud = 0
			a = 0
			if menor == 1000:
				return -1
		return menor


class Solution:

	def palop1(self, temp, i, m):
		low = 0
		high = len(temp) - 1
		pal = 0
		while low <= high:
			if temp[low] != temp[high]:
				if low >= i and high <= i + m - 1:
					return 1000000000.0
				pal += 1
			low += 1
			high -= 1
		return pal

	def specialPalindrome(self, s1, s2):
		n = len(s1)
		m = len(s2)
		mini = 1000000000.0
		for i in range(n - m + 1):
			temp = list(s1)
			op = 0
			for j in range(m):
				if temp[i + j] != s2[j]:
					op += 1
					temp[i + j] = s2[j]
			op = op + self.palop1(temp, i, m)
			mini = min(mini, op)
		if mini == 1000000000.0:
			return -1
		return mini


class Solution:

	def specialPalindrome(self, s1, s2):
		ls1 = [i for i in s1]
		ls2 = [i for i in s2]
		n = len(ls1)
		m = len(ls2)

		def minConvert(a, bl, br):
			c = 0
			(l, r) = (0, n - 1)
			while l <= r:
				if a[l] != a[r]:
					if (l >= bl and l <= br) and (r >= bl and r <= br):
						return -1
					c += 1
				(l, r) = (l + 1, r - 1)
			return c
		MAX = 1e+100
		solve = MAX
		test = [x for x in ls1]
		for i in range(n):
			if i + m - 1 >= n:
				break
			c = 0
			for k in range(m):
				if test[i + k] != ls2[k]:
					c += 1
					test[i + k] = ls2[k]
			cx = minConvert(test, i, i + m - 1)
			if cx >= 0:
				solve = min(solve, cx + c)
			for k in range(m):
				test[i + k] = ls1[i + k]
		return solve if solve != MAX else -1