Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Example:
ab: Number of insertions required is 1. bab or aba
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd
Example 1:
Input:
abcd
Output:
3
Explanation:
Here we can append 3 characters in the 
beginning,and the resultant string will 
be a palindrome ("dcbabcd").
Example 2:
Input:
aba
Output:
0
Explanation:
Given string is already a pallindrome hence
no insertions are required.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMinInsertions() which takes string S as input parameters and returns minimimum numser of insertions required.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|^{2})
Constraints:
1 ≤ |S| ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def findMinInsertions(self, S):
        # code here

Solutions:
class Solution:

	def findMinInsertions(self, S):
		m = len(S)
		b = S[::-1]
		n = len(b)
		t = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S[i - 1] == b[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		lps = t[m][n]
		return len(S) - lps


class Solution:

	def lcs(self, str1, str2):
		lcsMatrix = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
		for x in range(len(str1) + 1):
			for y in range(len(str2) + 1):
				if x == 0 or y == 0:
					lcsMatrix[x][y] = 0
				elif str1[x - 1] == str2[y - 1]:
					lcsMatrix[x][y] = 1 + lcsMatrix[x - 1][y - 1]
				else:
					lcsMatrix[x][y] = max(lcsMatrix[x - 1][y], lcsMatrix[x][y - 1])
		return lcsMatrix[len(str1)][len(str2)]

	def findMinInsertions(self, S):
		return len(S) - self.lcs(S, S[::-1])


class Solution:

	def findMinInsertions(self, text1):
		text2 = text1[::-1]
		next = [0 for col in range(len(text2) + 1)]
		for i in range(len(text1) - 1, -1, -1):
			curr = [0 for row in range(len(text2) + 1)]
			for j in range(len(text2) - 1, -1, -1):
				ans = 0
				if text1[i] == text2[j]:
					ans = 1 + next[j + 1]
				else:
					ans = max(next[j], curr[j + 1])
				curr[j] = ans
			next = curr
		return len(text1) - next[0]


class Solution:

	def solveTab(self, a, b):
		dp = [[0 for col in range(len(b) + 1)] for row in range(len(a) + 1)]
		for i in range(len(a) - 1, -1, -1):
			for j in range(len(b) - 1, -1, -1):
				ans = 0
				if a[i] == b[j]:
					ans = 1 + dp[i + 1][j + 1]
				else:
					ans = max(dp[i + 1][j], dp[i][j + 1])
				dp[i][j] = ans
		return dp[0][0]

	def findMinInsertions(self, text1):
		text2 = text1[::-1]
		return len(text1) - self.solveTab(text1, text2)


class Solution:

	def findMinInsertions(self, s1):
		x = len(s1)
		y = x
		s2 = s1[::-1]
		dp = [[-1 for i in range(y)] for j in range(x)]

		def answer(i, j, s1, s2):
			if i == -1 or j == -1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				dp[i][j] = 1 + answer(i - 1, j - 1, s1, s2)
				return dp[i][j]
			else:
				dp[i][j] = max(answer(i, j - 1, s1, s2), answer(i - 1, j, s1, s2))
				return dp[i][j]
		return x - answer(x - 1, y - 1, s1, s2)


class Solution:

	def findMinInsertions(self, S):
		tmp = S[::-1]
		n = len(S)
		dp = [[0] * (n + 1) for i in range(n + 1)]
		if tmp == S:
			return 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if S[i - 1] == tmp[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return n - dp[-1][-1]


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		temp = ''
		for i in range(n - 1, -1, -1):
			temp += S[i]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif S[i - 1] == temp[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = dp[n][n]
		return n - ans


class Solution:

	def get(self, i, j, dp, s):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i] == s[j]:
			ans = self.get(i + 1, j - 1, dp, s)
		else:
			ans = 1 + min(self.get(i + 1, j, dp, s), self.get(i, j - 1, dp, s))
		dp[i][j] = ans
		return ans

	def findMinInsertions(self, s):
		n = len(s)
		dp = []
		for i in range(0, n + 1):
			inner_arr = [-1 for i in range(0, n + 1)]
			dp.append(inner_arr)
		return self.get(0, n - 1, dp, s)


class Solution:

	def lcs(self, a, b):
		m = len(a)
		n = len(b)
		t = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if a[i - 1] == b[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		return t[m][n]

	def findMinInsertions(self, s):
		lps = self.lcs(s, s[::-1])
		return len(s) - lps


class Solution:

	def findMinInsertions(self, S):
		s1 = S
		s2 = s1[::-1]

		def lps(s1, s2, m, n):
			dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
			for i in range(n + 1):
				for j in range(m + 1):
					if i == 0 or j == 0:
						dp[i][j] == 0
			for i in range(1, n + 1):
				for j in range(1, m + 1):
					if s1[j - 1] == s2[i - 1]:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			return dp[n][m]
		return len(s1) - lps(s1, s2, len(s1), len(s2))


class Solution:

	def findMinInsertions(self, S):
		l = len(S)
		dp = [[float('inf') for _ in range(l + 1)] for _ in range(l + 1)]
		dp[l][l] = 0
		for i in range(l):
			dp[i][i] = 0
			dp[i][i + 1] = 0
		for size in range(2, l + 1):
			for i in range(0, l - size + 1):
				if S[i] == S[i + size - 1]:
					dp[i][i + size] = dp[i + 1][i + size - 1]
				else:
					dp[i][i + size] = min(dp[i + 1][i + size], dp[i][i + size - 1]) + 1
		return dp[0][l]


class Solution:

	def findMinInsertions(self, s):
		s1 = s[::-1]
		n = len(s)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s[i - 1] == s1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		res = n - dp[n][n]
		return res


class Solution:

	def findMinInsertions(self, s):
		n = len(s)
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = 0
		for l in range(2, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				if s[i] == s[j]:
					dp[i][j] = dp[i + 1][j - 1]
				else:
					dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
		return dp[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		t = [[0 for _ in range(n)] for _ in range(n)]
		gap = 0
		for gap in range(1, n):
			l = 0
			for h in range(gap, n):
				if S[l] == S[h]:
					t[l][h] = t[l + 1][h - 1]
				else:
					t[l][h] = min(t[l + 1][h], t[l][h - 1]) + 1
				l += 1
		return t[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		return self.findMinInsertionsLCS(S, len(S))

	def findMinInsertionsLCS(self, Str, n):
		revString = Str[::-1]
		return n - self.lcs(Str, revString, n, n)

	def lcs(self, X, Y, m, n):
		L = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					L[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					L[i][j] = L[i - 1][j - 1] + 1
				else:
					L[i][j] = max(L[i - 1][j], L[i][j - 1])
		return L[m][n]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
		for i in range(1, len(s1) + 1):
			for j in range(1, len(s2) + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[len(s1)][len(s2)]

	def longestPalinSubseq(self, S):
		S1 = S[::-1]
		n = len(S)
		return self.lcs(n, n, S, S1)

	def findMinInsertions(self, S):
		n = self.longestPalinSubseq(S)
		return len(S) - n


class Solution:

	def findMinInsertions(self, S):
		dp = [[-1 for i in range(len(S))] for j in range(len(S))]

		def recursive(S, left=0, right=len(S) - 1):
			if left >= right:
				return 0
			if dp[left][right] != -1:
				return dp[left][right]
			if S[left] == S[right]:
				dp[left][right] = recursive(S, left + 1, right - 1)
			else:
				dp[left][right] = 1 + min(recursive(S, left, right - 1), recursive(S, left + 1, right))
			return dp[left][right]
		return recursive(S)


class Solution:

	def lcs(self, X, Y, m, n, dp):
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]

	def findMinInsertions(self, S):
		n = len(S)
		look = [[0 for i in range(n + 1)] for i in range(n + 1)]
		a = self.lcs(S, S[::-1], n, n, look)
		return n - a


class Solution:

	def findMinInsertions(self, S):
		(n, m, t) = (len(S), len(S), S[::-1])
		dp = [[-1] * (n + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif S[i - 1] == t[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		l = dp[-1][-1]
		return n - l


class Solution:

	def lcs(self, X, Y):
		dp = [[0 for i in range(len(Y) + 1)] for j in range(len(X) + 1)]
		for i in range(len(X) + 1):
			for j in range(len(Y) + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[len(X)][len(Y)]

	def findMinInsertions(self, S):
		x = self.lcs(S, S[::-1])
		return len(S) - x


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		dp = [[0 for i in range(n)] for j in range(n)]
		for gap in range(n):
			for i in range(n - gap):
				j = i + gap
				if i == j:
					dp[i][j] = 0
				elif S[i] == S[j]:
					if i + 1 == j:
						dp[i][j] = 0
					else:
						dp[i][j] = dp[i + 1][j - 1]
				else:
					dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
		return dp[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		text1 = S
		text2 = S[::-1]
		n = len(text1)
		m = len(text2)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return n - dp[n][m]


class Solution:

	def findMinInsertions(self, S):
		return self.helper(S, {})

	def helper(self, s, store):
		if len(s) <= 1:
			return 0
		if s in store:
			return store[s]
		if s[0] == s[-1]:
			store[s] = self.helper(s[1:-1], store)
			return store[s]
		left = self.helper(s[1:], store) + 1
		right = self.helper(s[:-1], store) + 1
		store[s] = min(left, right)
		return store[s]


class Solution:

	def solve(self, S, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if S[i] == S[j]:
			return self.solve(S, i + 1, j - 1, dp)
		else:
			dp[i][j] = 1 + min(self.solve(S, i + 1, j, dp), self.solve(S, i, j - 1, dp))
		return dp[i][j]

	def findMinInsertions(self, S):
		dp = [[-1 for _ in range(len(S))] for _ in range(len(S))]
		return self.solve(S, 0, len(S) - 1, dp)


class Solution:

	def findMinInsertions(self, S):
		dp = [[0 for i in range(len(S))] for j in range(len(S))]
		for k in range(len(S)):
			(i, j) = (0, k)
			while j < len(S):
				if k == 0:
					dp[i][j] = 1
				elif k == 1:
					if S[i] == S[j]:
						dp[i][j] = 2
					else:
						dp[i][j] = 1
				elif S[i] == S[j]:
					dp[i][j] = 2 + dp[i + 1][j - 1]
				else:
					dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
				i += 1
				j += 1
		return len(S) - dp[0][-1]


class Solution:

	def findMinInsertions(self, S):
		arr = [[-1 for i in range(len(S))] for j in range(len(S))]
		(i, j) = (0, len(S) - 1)
		res = self.lps(S, i, j, arr)
		return len(S) - res

	def lps(self, S, i, j, arr):
		if i > j:
			return 0
		if arr[i][j] != -1:
			return arr[i][j]
		same = 0
		if i == j:
			same = 1 + self.lps(S, i + 1, j - 1, arr)
		elif S[i] == S[j]:
			same = 2 + self.lps(S, i + 1, j - 1, arr)
		diff1 = self.lps(S, i + 1, j, arr)
		diff2 = self.lps(S, i, j - 1, arr)
		res = max(same, diff1, diff2)
		arr[i][j] = res
		return res


class Solution:

	def findMinInsertions(self, S):
		r = S[::-1]
		l1 = len(S)
		l2 = len(r)
		dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if S[i - 1] == r[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return l1 - dp[l1][l2]


class Solution:

	def findMinInsertions(self, S):
		a = S
		b = S[::-1]
		m = len(a)
		t = [[0 for i in range(m + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif a[i - 1] == b[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return m - t[m][m]


class Solution:

	def findMinInsertions(self, S):
		A = [[0 for i in range(len(S))] for j in range(len(S))]
		for j in range(len(S)):
			for i in range(j - 1, -1, -1):
				if S[i] == S[j]:
					A[i][j] = A[i + 1][j - 1]
				else:
					A[i][j] = min(A[i + 1][j] + 1, A[i][j - 1] + 1)
		return A[0][len(S) - 1]


class Solution:

	def findMinInsertions(self, s: str) -> int:
		dp = {}

		def recurse(l, r):
			if r <= l:
				return 0
			if (l, r) not in dp:
				if s[l] == s[r]:
					dp[l, r] = recurse(l + 1, r - 1)
				else:
					dp[l, r] = min(recurse(l + 1, r), recurse(l, r - 1)) + 1
			return dp[l, r]
		result = recurse(0, len(s) - 1)
		return result


class Solution:

	def lcs(self, s, s1):
		dp = [[0 for i in range(len(s) + 1)] for j in range(len(s) + 1)]
		for i in range(len(s) + 1):
			for j in range(len(s) + 1):
				if i == 0 or j == 0:
					continue
				if s[i - 1] == s1[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]

	def findMinInsertions(self, s):
		return len(s) - self.lcs(s, s[::-1])


class Solution:

	def lcs(self, x, y, m, n):
		t = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[i - 1] == y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]

	def findMinInsertions(self, S):
		a = S[::-1]
		r = self.lcs(S, a, len(a), len(a))
		return len(S) - r


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		S_rev = S[::-1]
		t = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if S[i - 1] == S_rev[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return n - t[n][n]


class Solution:

	def findMinInsertions(self, S):

		def lcs(s1, s2):
			(n, m) = (len(s1), len(s2))
			prev = [0] * (m + 1)
			s2 = ' ' + s2
			for i in range(n):
				dp = [0] * (m + 1)
				for j in range(1, m + 1):
					dp[j] = max(prev[j], dp[j - 1]) if s1[i] != s2[j] else 1 + prev[j - 1]
				prev = dp
			return prev[-1]
		return len(S) - lcs(S, S[::-1])


class Solution:

	def findMinInsertions(self, s):
		n = len(s)
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		rev_s = s[::-1]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s[i - 1] == rev_s[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = dp[n][n]
		if ans == 0:
			ans = n - 1
		return n - ans


class Solution:

	def findMinInsertions(self, s1):
		s2 = s1[::-1]
		m = len(s1)
		n = len(s2)
		t = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return m - t[m][n]


class Solution:

	def findMinInsertions(self, s):
		dp = [[-1 for i in range(len(s))] for j in range(len(s))]

		def memo(i, j):
			if i == j - 1:
				return 0 if s[i] == s[j] else 1
			if i == j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = memo(i + 1, j - 1)
			else:
				dp[i][j] = min(memo(i, j - 1), memo(i + 1, j)) + 1
			return dp[i][j]
		m = len(s)
		return memo(0, m - 1)


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		t = [[0] * (n + 1) for k in range(n + 1)]
		y = S[::-1]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif S[i - 1] == y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return n - t[n][n]


class Solution:

	def findMinInsertions(self, S):
		l = 0
		h = 0
		gap = 0
		n = len(S)
		dp = [[0] * n for i in range(n)]
		for gap in range(1, n):
			l = 0
			for h in range(gap, n):
				if S[l] == S[h]:
					dp[l][h] = dp[l + 1][h - 1]
				else:
					dp[l][h] = min(dp[l + 1][h], dp[l][h - 1]) + 1
				l += 1
		return dp[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		s1 = list(S)
		s2 = list(S[::-1])
		m = len(s1)
		dp = [[0] * (m + 1) for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return m - dp[m][m]


class Solution:

	def lcs(self, x, y):
		n = len(x)
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if x[i - 1] == y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][n]

	def findMinInsertions(self, S):
		rev = S[::-1]
		val = self.lcs(S, rev)
		return len(S) - val


class Solution:

	def findMinInsertions(self, str1):
		str2 = str1[::-1]
		(l1, l2) = (len(str1), len(str2))
		dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]

		def lcs():
			for i in range(l1 - 1, -1, -1):
				for j in range(l2 - 1, -1, -1):
					if str1[i] == str2[j]:
						dp[i][j] = 1 + dp[i + 1][j + 1]
					else:
						dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
			return dp[0][0]
		ans = lcs()
		return l1 - ans


class Solution:

	def findMinInsertions(self, s):
		n = len(s)
		mini = n - 1
		if n == 1:
			return 1
		dp = [[-1] * n for i in range(n)]

		def solve(i, j, dp):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = solve(i + 1, j - 1, dp)
			else:
				dp[i][j] = 1 + min(solve(i + 1, j, dp), solve(i, j - 1, dp))
			return dp[i][j]
		return solve(0, n - 1, dp)


class Solution:

	def findMinInsertions(self, s):
		n = len(s)
		dp = [[-1] * (n + 1) for _ in range(n + 1)]

		def form(i, j):
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = form(i + 1, j - 1)
				return dp[i][j]
			dp[i][j] = 1 + min(form(i + 1, j), form(i, j - 1))
			return dp[i][j]


class Solution:

	def findMinInsertions(self, s1):
		reverse_s1 = s1[::-1]
		n = len(s1)
		m = len(reverse_s1)
		dp = [[-1 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(m + 1):
			dp[0][i] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == reverse_s1[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					include_s1 = dp[i][j - 1]
					include_s2 = dp[i - 1][j]
					dp[i][j] = max(include_s1, include_s2)
		return len(s1) - dp[n][m]


class Solution:

	def findMinInsertions(self, S):

		def makePal(s, e, ar):
			if s > e:
				return float('+inf')
			elif s == e:
				return 0
			elif s == e - 1:
				if S[s] == S[e]:
					return 0
				else:
					return 1
			elif ar[s][e] != -1:
				return ar[s][e]
			elif S[s] == S[e]:
				ar[s][e] = makePal(s + 1, e - 1, ar)
				return ar[s][e]
			elif S[s] != S[e]:
				ar[s][e] = 1 + min(makePal(s + 1, e, ar), makePal(s, e - 1, ar))
				return ar[s][e]
		ar = [[-1 for j in range(len(S))] for i in range(len(S))]
		makePal(0, len(S) - 1, ar)
		return ar[0][len(S) - 1]


class Solution:

	def findMinInsertions(self, S):
		s1 = S[::-1]
		n = len(S)

		def lcs(i, j, s1, dp):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if S[i] == s1[j]:
				dp[i][j] = 1 + lcs(i - 1, j - 1, s1, dp)
			else:
				dp[i][j] = max(lcs(i - 1, j, s1, dp), lcs(i, j - 1, s1, dp))
			return dp[i][j]
		dp = [[-1 for i in range(n)] for j in range(n)]
		len_lcs = lcs(n - 1, n - 1, s1, dp)
		return n - len_lcs


class Solution:

	def findMinInsertions(self, S):
		str1 = S
		str2 = S[::-1]
		memory = []
		for x in range(len(str1) + 1):
			list1 = []
			for y in range(len(str2) + 1):
				list1.append(-1)
			memory.append(list1)
		for i in range(len(str1) + 1):
			for j in range(len(str2) + 1):
				if i == 0 or j == 0:
					memory[i][j] = 0
				elif str1[i - 1] == str2[j - 1]:
					memory[i][j] = memory[i - 1][j - 1] + 1
				elif str1[i - 1] != str2[j - 1]:
					memory[i][j] = max(memory[i - 1][j], memory[i][j - 1])
		lenOfLCS = memory[len(str1)][len(str2)]
		return abs(len(str1) - lenOfLCS)


class Solution:

	def findMinInsertions(self, s):
		n = len(s)
		if n == 0:
			return 0
		t = [[0 for j in range(n)] for i in range(n)]
		for cl in range(2, n + 1):
			for i in range(n - cl + 1):
				j = i + cl - 1
				if s[i] == s[j] and cl == 2:
					t[i][j] = 0
				elif s[i] == s[j]:
					t[i][j] = t[i + 1][j - 1]
				else:
					t[i][j] = 1 + min(t[i][j - 1], t[i + 1][j])
		return t[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		s = S
		t = S[::-1]
		n = len(S)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]

		def lcs():
			for i in range(1, n + 1):
				for j in range(1, n + 1):
					if s[i - 1] == t[j - 1]:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			return dp[n][n]
		return n - lcs()


class Solution:

	def findMinInsertions(self, S):
		S1 = S
		S2 = S[::-1]
		m = len(S1)
		n = len(S2)
		dp = [[-1 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[m][n]
		return abs(lcs - m)


class Solution:

	def findMinInsertions(self, S):
		s = S[::-1]
		dp = [[None] * (len(s) + 1) for i in range(len(s) + 1)]
		for i in range(len(s) + 1):
			dp[i][0] = 0
		for i in range(len(s) + 1):
			dp[0][i] = 0
		for i in range(1, len(s) + 1):
			for j in range(1, len(s) + 1):
				if S[i - 1] == s[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[len(s)][len(s)]
		ins = len(s) - lcs
		return ins


def f(i, j, s, dp):
	if i < j:
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i] == s[j]:
			dp[i][j] = f(i + 1, j - 1, s, dp)
			return f(i + 1, j - 1, s, dp)
		dp[i][j] = 1 + min(f(i + 1, j, s, dp), f(i, j - 1, s, dp))
		return 1 + min(f(i + 1, j, s, dp), f(i, j - 1, s, dp))
	else:
		return 0

class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		dp = [[-1 for i in range(n)] for j in range(n)]
		return f(0, n - 1, S, dp)


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(0, n):
			dp[i][i] = 1
		for move in range(0, n):
			row = 0
			for col in range(move, n):
				if row != col:
					if S[row] == S[col]:
						dp[row][col] = 2 + dp[row + 1][col - 1]
					else:
						dp[row][col] = max(dp[row + 1][col], dp[row][col - 1])
				row += 1
		return n - dp[0][-1]


class Solution:

	def findMinInsertions(self, S):
		n = len(S)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]

		def recur(i, j):
			if i > j:
				return 0
			if i == j:
				dp[i][j] = 1
				return 1
			if dp[i][j]:
				return dp[i][j]
			if S[i] == S[j]:
				dp[i][j] = 2 + recur(i + 1, j - 1)
				return dp[i][j]
			dp[i][j] = max(recur(i + 1, j), recur(i, j - 1))
			return dp[i][j]
		recur(0, n - 1)
		return n - dp[0][n - 1]


class Solution:

	def findMinInsertions(self, S):
		if S == S[::-1]:
			return 0
		else:

			def lcs(a, b):
				n = len(a)
				dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
				for i in range(1, n + 1):
					for j in range(1, n + 1):
						if a[i - 1] == b[j - 1]:
							dp[i][j] = dp[i - 1][j - 1] + 1
						else:
							dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
				return dp[n][n]
			return len(S) - lcs(S, S[::-1])


class Solution:

	def findMinInsertions(self, S):
		x = S
		y = S[::-1]
		n = len(x)
		m = len(y)
		dp = [[-1 for i in range(m + 1)] for j in range(m + 1)]

		def rec(i, j):
			if i >= n or j >= m:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if x[i] == y[j]:
				dp[i][j] = 1 + rec(i + 1, j + 1)
			else:
				dp[i][j] = max(rec(i, j + 1), rec(i + 1, j))
			return dp[i][j]
		ans = rec(0, 0)
		return n - ans


class Solution:

	def longestCommonSubsequence(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]

	def longestPalinSubseq(self, s):
		return self.longestCommonSubsequence(s, s[::-1])

	def findMinInsertions(self, s):
		return len(s) - self.longestPalinSubseq(s)


class Solution:

	def findMinInsertions(self, S):

		def lcs(x, y, s1, s2):
			dp = []
			for i in range(x + 1):
				dp.append([0] * (y + 1))
			for i in range(x):
				for j in range(y):
					ans = 0
					if s1[i] == s2[j]:
						ans = 1 + dp[i][j]
					else:
						ans = max(dp[i + 1][j], dp[i][j + 1])
					dp[i + 1][j + 1] = ans
			return dp[x][y]
		Sn = ''.join(reversed(S))
		return len(S) - lcs(len(S), len(S), S, Sn)


class Solution:

	def findMinInsertions(self, S):
		str = S
		str2 = S[::-1]
		x = len(str)
		t = [[-1] * (x + 1) for j in range(x + 1)]
		for i in range(0, x + 1):
			for j in range(0, x + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, x + 1):
			for j in range(1, x + 1):
				if str[i - 1] == str2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return len(S) - t[-1][-1]


class Solution:

	def findMinInsertions(self, S):
		lps = self.LPS(S)
		if lps == 0:
			return len(S) - 1
		return len(S) - lps

	def LPS(self, S):
		a = S
		b = S[::-1]
		return self.LCS(a, b)

	def LCS(self, a, b):
		table = [[0 for _ in range(len(a) + 1)] for _ in range(len(b) + 1)]
		for i in range(1, len(table)):
			for j in range(1, len(table[0])):
				if a[i - 1] == b[j - 1]:
					table[i][j] = 1 + table[i - 1][j - 1]
				else:
					table[i][j] = max(table[i - 1][j], table[i][j - 1])
		return table[-1][-1]