Given a string of S as input. Your task is to write a program to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome.
Note: The order of characters in the string should be maintained.
Example 1:
Input: S = "aebcbda"
Output: 2
Explanation: Remove characters 'e' 
and 'd'.
Example 2:
Input: S = "geeksforgeeks"
Output: 8
Explanation: One of the possible result
string can be "eefee", so answer is 
13 - 5 = 8.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumNumberOfDeletions() which takes the string S as inputs and returns the minimum number of deletions required to convert S into a pallindrome.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|^{2})
Constraints:
1 ≤ |S| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def minimumNumberOfDeletions(self,S):

        # code here 

Solutions:
class Solution:

	def minimumNumberOfDeletions(self, s1):
		s2 = s1[::-1]
		n = len(s1)

		def answer(i, j):
			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)
				return dp[i][j]
			dp[i][j] = max(answer(i - 1, j), answer(i, j - 1))
			return dp[i][j]
		dp = [[-1 for i in range(n)] for j in range(n)]
		x = answer(n - 1, n - 1)
		return n - x


class Solution:

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


class Solution:

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		rev_s = S[::-1]
		m = len(S)
		n = m
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, m + 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])
		return len(S) - dp[m][n]


class Solution:

	def minimumNumberOfDeletions(self, S):
		self.S = S
		n = len(S)
		dp = [[-1 for j in range(n)] for i in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if i >= j:
					dp[i][j] = 0
					continue
				if S[i] == S[j]:
					dp[i][j] = dp[i + 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i][j - 1], dp[i + 1][j])
		return dp[0][n - 1]

	def palin(self, i, j):
		if i >= j:
			return 0
		(count1, count2) = (float('inf'), float('inf'))
		count = float('inf')
		if self.S[i] == self.S[j]:
			count = self.palin(i + 1, j - 1)
		else:
			count1 = 1 + self.palin(i, j - 1)
			count2 = 1 + self.palin(i + 1, j)
		return min(count1, count2, count)


class Solution:

	def delete(s, smap):
		if s == s[::-1]:
			return 0
		if smap.get(s, -1) == -1:
			(i, j) = (0, len(s) - 1)
			while s[i] == s[j]:
				i += 1
				j -= 1
			if s[i] != s[j]:
				l = Solution.delete(s[i + 1:j + 1], smap)
				r = Solution.delete(s[i:j], smap)
				smap[s] = min(r, l) + 1
		return smap[s]

	def minimumNumberOfDeletions(self, S):
		smap = {}
		return Solution.delete(S, smap)


class Solution:

	def minimumNumberOfDeletions(self, S):
		memo = {}

		def dfs(i, j, s):
			if i >= j:
				return 0
			if (i, j) in memo:
				return memo[i, j]
			if s[i] != s[j]:
				memo[i, j] = 1 + min(dfs(i + 1, j, s), dfs(i, j - 1, s))
			else:
				memo[i, j] = dfs(i + 1, j - 1, s)
			return memo[i, j]
		return dfs(0, len(S) - 1, S)


class Solution:

	def minimumNumberOfDeletions(self, S):
		res = [[0 for y in range(len(S))] for x in range(len(S))]
		for a in range(len(S)):
			res[a][a] = 1
		n = len(S)
		for pl in range(2, n + 1):
			for i in range(n - pl + 1):
				j = i + pl - 1
				if S[i] == S[j] and pl == 2:
					res[i][j] = 2
				elif S[i] == S[j]:
					res[i][j] = res[i + 1][j - 1] + 2
				else:
					res[i][j] = max(res[i + 1][j], res[i][j - 1])
		return n - res[0][n - 1]


class Solution:

	def minimumNumberOfDeletions(self, S):

		def lps(i, j):
			if i > j:
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			a = b = c = 0
			if S[i] == S[j]:
				if i != j:
					a = lps(i + 1, j - 1) + 2
				else:
					a = 1
			b = lps(i + 1, j)
			c = lps(i, j - 1)
			dp[i][j] = max(a, b, c)
			return dp[i][j]
		dp = [[0 for i in range(len(S))] for j in range(len(S))]
		return len(S) - lps(0, len(S) - 1)


class Solution:

	def minimumNumberOfDeletions(self, S):
		t = [[-1 for i in range(len(S) + 1)] for _ in range(len(S) + 1)]

		def Lcs(x, y, n, m):
			for i in range(n + 1):
				for j in range(m + 1):
					if i == 0 or j == 0:
						t[i][j] = 0
			for i in range(1, n + 1):
				for j in range(1, m + 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[n][m]
		s2 = list(S)
		s1 = ''.join(s2[::-1])
		deletion = len(S) - Lcs(S, s1, len(S), len(S))
		return deletion


class Solution:

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


class Solution:

	def lcs(self, S):
		n = len(S)
		res = [[0 for x in range(n)] for y in range(n)]
		for i in range(n):
			res[i][i] = 1
		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:
					res[i][j] = 2
				elif S[i] == S[j]:
					res[i][j] = res[i + 1][j - 1] + 2
				else:
					res[i][j] = max(res[i][j - 1], res[i + 1][j])
		return res[0][n - 1]

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		l = self.lcs(S)
		return n - l


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		P = S[::-1]
		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] == P[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		a = dp[n][n]
		return n - a


class Solution:

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		dp = [[None for i in range(len(S) + 1)] for j in range(len(S) + 1)]
		rev = S[::-1]
		for i in range(len(S) + 1):
			for j in range(len(S) + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, len(S) + 1):
			for j in range(1, len(S) + 1):
				if S[i - 1] == rev[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 len(S) - dp[len(S)][len(S)]


class Solution:

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		temp = [[0 for i in range(len(S) + 1)] for j in range(len(S) + 1)]
		rev = S[::-1]
		for i in range(1, len(S) + 1):
			for j in range(1, len(S) + 1):
				if rev[i - 1] == S[j - 1]:
					temp[i][j] = temp[i - 1][j - 1] + 1
				else:
					temp[i][j] = max(temp[i - 1][j], temp[i][j - 1])
		return len(S) - temp[-1][-1]


class Solution:

	def minimumNumberOfDeletions(self, s):
		dp = [[0 for i in range(len(s))] for j in range(len(s))]

		def minimum(s, i, j):
			if i > j:
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			if s[i] == s[j] and i == j:
				dp[i][j] = 1 + minimum(s, i + 1, j - 1)
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = 2 + minimum(s, i + 1, j - 1)
				return dp[i][j]
			dp[i][j] = max(minimum(s, i + 1, j), minimum(s, i, j - 1))
			return dp[i][j]
		z = minimum(s, 0, len(s) - 1)
		return len(s) - z


class Solution:

	def findlcs(self, s1, s2, i, j, dp):
		if i >= len(s1) or j >= len(s2):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s1[i] == s2[j]:
			dp[i][j] = 1 + self.findlcs(s1, s2, i + 1, j + 1, dp)
		else:
			dp[i][j] = max(self.findlcs(s1, s2, i + 1, j, dp), self.findlcs(s1, s2, i, j + 1, dp))
		return dp[i][j]

	def minimumNumberOfDeletions(self, s1):
		s2 = s1[::-1]
		dp = [[-1 for _ in range(len(s1) + 1)] for _ in range(len(s2) + 1)]
		return len(s1) - self.findlcs(s1, s2, 0, 0, dp)


class Solution:

	def minimumNumberOfDeletions(self, S):
		ans = 0
		dp = []
		for i in range(len(S)):
			a = []
			for j in range(len(S)):
				a.append(0)
			dp.append(a)
		for i in range(len(S)):
			j = 0
			k = i
			while k < len(S):
				if i == 0:
					dp[j][k] = 1
				elif i == 1 and S[j] == S[k]:
					dp[j][k] = 2
				elif S[j] == S[k] and dp[j + 1][k - 1] != 0:
					dp[j][k] = dp[j + 1][k - 1] + 2
				else:
					dp[j][k] = max(dp[j + 1][k], dp[j][k - 1])
				ans = max(ans, dp[j][k])
				j = j + 1
				k = k + 1
		return len(S) - ans


class Solution:

	def minimumNumberOfDeletions(self, S):
		s = S[::-1]
		(x, y) = (len(S), len(s))

		def lcs(S, s, x, y, dp):
			if x == 0 or y == 0:
				return 0
			if dp[x][y] != -1:
				return dp[x][y]
			elif S[x - 1] == s[y - 1]:
				dp[x][y] = 1 + lcs(S, s, x - 1, y - 1, dp)
				return dp[x][y]
			dp[x][y] = max(lcs(S, s, x, y - 1, dp), lcs(S, s, x - 1, y, dp))
			return dp[x][y]
		dp = [[-1 for i in range(y + 1)] for j in range(x + 1)]
		h = lcs(S, s, x, y, dp)
		return len(S) - h


class Solution:

	def minimumNumberOfDeletions(self, string):
		revS = S[::-1]
		arr = [[0 for j in range(len(S) + 1)] for i in range(len(S) + 1)]
		for i in range(1, len(S) + 1):
			for j in range(1, len(S) + 1):
				if S[i - 1] == revS[j - 1]:
					arr[i][j] = arr[i - 1][j - 1] + 1
				else:
					arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
		return len(S) - arr[-1][-1]


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		isPalindrome = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			isPalindrome[i][i] = 1
		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:
					isPalindrome[i][j] = 2
				elif S[i] == S[j]:
					isPalindrome[i][j] = isPalindrome[i + 1][j - 1] + 2
				else:
					isPalindrome[i][j] = max(isPalindrome[i][j - 1], isPalindrome[i + 1][j])
		return n - isPalindrome[0][n - 1]


class Solution:

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


class Solution:

	def recur(self, i, j, s, dp):
		try:
			if i >= j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == s[j]:
				dp[i][j] = self.recur(i + 1, j - 1, s, dp)
				return dp[i][j]
			else:
				dp[i][j] = 1 + min(self.recur(i + 1, j, s, dp), self.recur(i, j - 1, s, dp))
				return dp[i][j]
		except Exception as e:
			print('E', e)

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		count = self.recur(0, len(S) - 1, S, dp)
		return count


class Solution:

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

	def helper(self, S, store):
		if S in store:
			return store[S]
		if S == S[::-1]:
			store[S] = 0
			return 0
		if S[0] == S[-1]:
			store[S] = self.helper(S[1:-1], store)
			return store[S]
		output1 = self.helper(S[1:], store)
		output2 = self.helper(S[:-1], store)
		store[S] = min(output1, output2) + 1
		return store[S]


class Solution:

	def lcs_helper(self, i, j, s1, s2, n1, n2, dp):
		if dp[i][j] != -1:
			return dp[i][j]
		if i == n1 or j == n2:
			return 0
		if s1[i] == s2[j]:
			dp[i][j] = 1 + self.lcs_helper(i + 1, j + 1, s1, s2, n1, n2, dp)
		else:
			dp[i][j] = max(self.lcs_helper(i + 1, j, s1, s2, n1, n2, dp), self.lcs_helper(i, j + 1, s1, s2, n1, n2, dp))
		return dp[i][j]

	def lcs(self, x, y, s1, s2):
		n1 = len(s1)
		n2 = len(s2)
		n = max(n1, n2)
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.lcs_helper(0, 0, s1, s2, n1, n2, dp)

	def minimumNumberOfDeletions(self, S):
		lcs_length = self.lcs(0, 0, S, S[::-1])
		return len(S) - lcs_length


class Solution:

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			dp[i][i] = 0
		for length in range(2, n + 1):
			for i in range(n + 1 - length):
				j = i + length - 1
				if S[i] == S[j] and length == 2:
					dp[i][j] = 0
				elif 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 lcs(self, s, s2, 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
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s[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 minimumNumberOfDeletions(self, S):
		S2 = S[::-1]
		dp = [[-1 for i in range(len(S2) + 1)] for j in range(len(S) + 1)]
		return len(S) - self.lcs(S, S2, len(S), len(S2), dp)


class Solution:

	def getLCS(self, index1, index2, s1, s2, dp):
		if index1 < 0 or index2 < 0:
			return 0
		take = 0
		if dp[index1][index2] != -1:
			return dp[index1][index2]
		if s1[index1] == s2[index2]:
			take = 1 + self.getLCS(index1 - 1, index2 - 1, s1, s2, dp)
		nottake = max(self.getLCS(index1 - 1, index2, s1, s2, dp), self.getLCS(index1, index2 - 1, s1, s2, dp))
		dp[index1][index2] = max(take, nottake)
		return dp[index1][index2]

	def minimumNumberOfDeletions(self, S1):
		S2 = S1[::-1]
		dp = [[-1 for i in range(len(S1))] for j in range(len(S2))]
		lcs = self.getLCS(len(S1) - 1, len(S2) - 1, S1, S2, dp)
		return len(S1) - lcs


class Solution:

	def minimumNumberOfDeletions(self, S):
		l = len(S)
		matrix = [[0 for x in range(l)] for y in range(l)]
		for i in range(l):
			matrix[i][i] = 1
		for c1 in range(2, l + 1):
			for i in range(l - c1 + 1):
				j = i + c1 - 1
				if S[i] == S[j] and c1 == 2:
					matrix[i][j] = 2
				elif S[i] == S[j]:
					matrix[i][j] = matrix[i + 1][j - 1] + 2
				else:
					matrix[i][j] = max(matrix[i + 1][j], matrix[i][j - 1])
		return l - matrix[0][l - 1]


class Solution:

	def minimumNumberOfDeletions(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(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif 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])
		lcs = dp[n][n]
		return n - lcs


class Solution:

	def minimumNumberOfDeletions(self, s):

		def de(i, j):
			if i >= j:
				return 0
			key = (i, j)
			if key not in dp:
				if s[i] == s[j]:
					return de(i + 1, j - 1)
				else:
					res = 1 + min(de(i + 1, j), de(i, j - 1))
					dp[key] = res
			return dp[key]
		dp = {}
		return de(0, len(s) - 1)


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		a = S[::-1]
		t = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if S[i - 1] == a[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 minimumNumberOfDeletions(self, S):
		memoize = []
		length = len(S)
		for i in range(length + 1):
			temp = []
			for j in range(length + 1):
				temp.append(-1)
			memoize.append(temp)
		return length - self.minimumDeletion(length, length, S, S[::-1], memoize)

	def minimumDeletion(self, index1, index2, str, revStr, memoize):
		if memoize[index1][index2] != -1:
			return memoize[index1][index2]
		if index1 == 0 or index2 == 0:
			return 0
		if str[index1 - 1] == revStr[index2 - 1]:
			memoize[index1][index2] = 1 + self.minimumDeletion(index1 - 1, index2 - 1, str, revStr, memoize)
			return memoize[index1][index2]
		memoize[index1][index2] = max(self.minimumDeletion(index1, index2 - 1, str, revStr, memoize), self.minimumDeletion(index1 - 1, index2, str, revStr, memoize))
		return memoize[index1][index2]


class Solution:

	def lcsUtility(self, s1, s2, index1, index2, dp):
		if index1 == -1 or index2 == -1:
			return 0
		if dp[index1][index2] != -1:
			return dp[index1][index2]
		if s1[index1] == s2[index2]:
			dp[index1][index2] = 1 + self.lcsUtility(s1, s2, index1 - 1, index2 - 1, dp)
		else:
			dp[index1][index2] = max(self.lcsUtility(s1, s2, index1 - 1, index2, dp), self.lcsUtility(s1, s2, index1, index2 - 1, dp))
		return dp[index1][index2]

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for j in range(y)] for i in range(x)]
		return self.lcsUtility(s1, s2, x - 1, y - 1, dp)

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


import collections
from collections import Counter

class Solution:

	def minimumNumberOfDeletions(self, S):

		def helper(S, i, j):
			if i >= j:
				return 0
			if (i, j) not in hash:
				if S[i] == S[j]:
					hash[i, j] = helper(S, i + 1, j - 1)
				else:
					hash[i, j] = 1 + min(helper(S, i + 1, j), helper(S, i, j - 1))
			return hash[i, j]
		hash = {}
		return helper(S, 0, len(S) - 1)


class Solution:

	def minimumNumberOfDeletions(self, s):
		n = len(s)
		l = self.lcs(s)
		return n - l

	def lcs(self, s):
		rev = self.rvrse(s)
		n = len(s)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if s[i] == rev[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]

	def rvrse(self, s):
		rev = ''
		for i in s:
			rev = i + rev
		return rev


class Solution:

	def longestPalseq(self, i, j, len1, text1, text2, dic):
		ans = 0
		if i >= len1 or j >= len1:
			return 0
		if (i, j) not in dic:
			if text1[i] == text2[j]:
				ans = max(ans, 1 + self.longestPalseq(i + 1, j + 1, len1, text1, text2, dic))
				dic[i, j] = ans
			else:
				dic[i, j] = max(self.longestPalseq(i, j + 1, len1, text1, text2, dic), self.longestPalseq(i + 1, j, len1, text1, text2, dic))
		return dic[i, j]

	def minimumNumberOfDeletions(self, S):
		len1 = len(S)
		S_Inv = S[::-1]
		len2 = self.longestPalseq(0, 0, len1, S, S_Inv, {})
		return len1 - len2


class Solution:

	def minimumNumberOfDeletions(self, Str):
		n = len(Str)
		str1 = Str[::-1]
		l = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i != 0 and j != 0:
					if Str[i - 1] == str1[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 n - l[n][n]


class Solution:

	def lcs(self, s, s1):
		m = len(s)
		t = [[0 for i in range(m + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, m + 1):
				if s[i - 1] == s1[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][m]

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		s1 = S[::-1]
		x = len(S)
		y = len(s1)
		dp = [[None] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				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 x - dp[x][y]


class Solution:

	def minimumNumberOfDeletions(self, s1):
		s2 = s1[::-1]
		(m, n) = (len(s1), len(s2))
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		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:
					option1 = dp[i - 1][j]
					option2 = dp[i][j - 1]
					dp[i][j] = max(option1, option2)
		return m - dp[m][n]


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		K = [[-1 for j in range(n + 1)] for i in range(n + 1)]

		def fun(self, i, j):
			if i == n or j == 0:
				return 0
			if K[i][j] != -1:
				return K[i][j]
			if S[i] == S[j - 1]:
				K[i][j] = 1 + fun(self, i + 1, j - 1)
				return K[i][j]
			else:
				K[i][j] = max(fun(self, i + 1, j), fun(self, i, j - 1))
				return K[i][j]
		return n - fun(self, 0, n)


class Solution:

	def minimumNumberOfDeletions(self, S):
		text1 = S
		text2 = S[::-1]
		m = len(text1)
		n = len(text2)
		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 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])
		lcs = dp[m][n]
		return abs(lcs - m)


class Solution:

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

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


class Solution:

	def minimumNumberOfDeletions(self, s1):
		m = len(s1)
		s2 = s1[::-1]
		n = len(s2)
		return m - self.lcs(s1, s2, m, n)

	def lcs(self, t1, t2, m, n):
		if m == 0 or n == 0:
			return 0
		dp = [[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 t1[i - 1] == t2[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]


class Solution:

	def minimumNumberOfDeletions(self, s):
		r = s[::-1]
		n = len(s)
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, len(dp)):
			for j in range(1, len(dp[0])):
				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 n - dp[n][n]


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		SR = S[::-1]
		t = [[-1] * (n + 1) for _ in range(n + 1)]
		return n - self.LCS(t, n, n, S, SR)

	def LCS(self, t, n, m, text1, text2):
		if n == 0 or m == 0:
			return 0
		if t[m][n] != -1:
			return t[m][n]
		if text1[n - 1] == text2[m - 1]:
			t[m][n] = 1 + self.LCS(t, n - 1, m - 1, text1, text2)
			return t[m][n]
		t[m][n] = max(self.LCS(t, n - 1, m, text1, text2), self.LCS(t, n, m - 1, text1, text2))
		return t[m][n]


class Solution:

	def minimumNumberOfDeletions(self, s):
		n = len(s)
		x = s
		y = s[::-1]
		t = [[0] * (n + 1) for _ 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]:
					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[i][j]


class Solution:

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

	def lcs(self, a, b, m, n):
		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 a[j - 1] == b[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[i][j]


class Solution:

	def minimumNumberOfDeletions(self, S):
		return self.util_dp(S)

	def util_dp(self, X):
		n = len(X)
		Y = X[::-1]
		lookup = [[0 for x in range(n + 1)] for y 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]:
					lookup[i][j] = lookup[i - 1][j - 1] + 1
				else:
					lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])
		return n - lookup[n][n]

	def util_memo(self, S, i, j, dp):
		if i >= j:
			return 0
		key = (i, j)
		if key not in dp:
			if S[i] == S[j]:
				dp[key] = self.util_memo(S, i + 1, j - 1, dp)
			else:
				dp[key] = 1 + min(self.util_memo(S, i + 1, j, dp), self.util_memo(S, i, j - 1, dp))
		print(dp)
		return dp[key]

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		dp = {}
		return self.util_memo(S, 0, len(S) - 1, dp)

	def util_dp(self, S, i, j, dp):
		if i >= len(S) or j >= len(S):
			return 0
		if S[i] == S[j]:
			dp[i][j] = 1 + self.util_dp(S, i + 1, j + 1, dp)
		if dp[i][j] != -1:
			return dp[i][j]
		else:
			dp[i][j] = max(self.util_dp(S, i, j + 1, dp), self.util_dp(S, i + 1, j, dp))
		return dp[-1][-1]

	def util_memo(self, S, i, j, dp):
		if i >= j:
			return 0
		key = (i, j)
		if key not in dp:
			if S[i] == S[j]:
				dp[key] = self.util_memo(S, i + 1, j - 1, dp)
			else:
				dp[key] = 1 + min(self.util_memo(S, i + 1, j, dp), self.util_memo(S, i, j - 1, dp))
		return dp[key]

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		m = len(S)
		S1 = S[::-1]
		n = len(S1)
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif 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 m - dp[m][n]


class Solution:

	def minimumNumberOfDeletions(self, S):
		x = y = len(S)
		a = S[::-1]
		t = [[0] * 1001 for i in range(1001)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if S[x - i] == a[y - j]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return x - t[x][y]


class Solution:

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


class Solution:

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


class Solution:

	def lcs(self, x, y, m, n):
		dp = [[0 for i in range(n + 1)] for i 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]:
					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 minimumNumberOfDeletions(self, S):
		s1 = S[::-1]
		m = len(S)
		n = len(s1)
		return m - self.lcs(S, s1, m, n)


class Solution:

	def minimumNumberOfDeletions(self, s):
		r = s[::-1]
		n = len(s)
		m = len(r)
		dp = [[None for _ 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
				elif 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 n - dp[i][j]


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		hm = {}

		def sol(l, r):
			if l == r:
				return 1
			if l > r:
				return 0
			if (l, r) in hm:
				return hm[l, r]
			if S[l] == S[r]:
				hm[l, r] = 2 + sol(l + 1, r - 1)
			else:
				hm[l, r] = max(sol(l, r - 1), sol(l + 1, r))
			return hm[l, r]
		return n - sol(0, n - 1)


class Solution:

	def minimumNumberOfDeletions(self, s):
		rev = s[::-1]
		n = len(s)
		dp = [[0 for x in range(n + 1)] for x in range(n + 1)]
		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] == rev[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = dp[n][n]
		return n - ans


class Solution:

	def lps(self, str):
		n = len(str)
		L = [[0 for x in range(n)] for y in range(n)]
		for i in range(n):
			L[i][i] = 1
		for cl in range(2, n + 1):
			for i in range(n - cl + 1):
				j = i + cl - 1
				if str[i] == str[j] and cl == 2:
					L[i][j] = 2
				elif str[i] == str[j]:
					L[i][j] = L[i + 1][j - 1] + 2
				else:
					L[i][j] = max(L[i][j - 1], L[i + 1][j])
		return L[0][n - 1]

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		l = self.lps(S)
		return n - l


class Solution:

	def minimumNumberOfDeletions(self, S):
		s2 = S[::-1]
		m = len(S)
		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 S[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][m]


class Solution:

	def minimumNumberOfDeletions(self, S):
		N = len(S)
		dp = [[0] * N for _ in range(N)]
		for i in range(N):
			dp[i][i] = 1
		for length in range(1, N):
			for start in range(0, N - length):
				end = start + length
				if S[start] == S[end]:
					if end - start == 1:
						dp[start][end] = 2
					else:
						dp[start][end] = 2 + dp[start + 1][end - 1]
				else:
					dp[start][end] = max(dp[start + 1][end], dp[start][end - 1])
		return N - max([dp[i][-1] for i in range(N)])


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		str1 = S
		str2 = S[::-1]
		t = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[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 n - t[-1][-1]


class Solution:

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


class Solution:

	def minimumNumberOfDeletions(self, S):
		n = len(S)
		x = S[::-1]
		y = [[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] == x[j - 1]:
					y[i][j] = y[i - 1][j - 1] + 1
				else:
					y[i][j] = max(y[i - 1][j], y[i][j - 1])
		return n - y[n][n]


class Solution:

	def minimumNumberOfDeletions(self, S):
		lps = LPS(S)
		ans = len(S) - lps
		return ans

def LPS(A):
	m = len(A)
	A_ = A[::-1]
	return LCS(A, A_, m, m)

def LCS(A, B, m, n):
	dp = [[-1] * (m + 1) for _ in range(n + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif A[i - 1] == B[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]


class Solution:

	def minimumNumberOfDeletions(self, A):
		B = A[::-1]
		n = len(A)
		T = [[0] * (n + 1) for i 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]:
					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 minimumNumberOfDeletions(self, S):
		s = S[::-1]
		dp = [[0] * (len(s) + 1) for i in range(1 + len(s))]
		for i in range(1 + len(s)):
			for j in range(1 + len(s)):
				if i == 0 or j == 0:
					continue
				elif 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])
		return len(s) - dp[-1][-1]


class Solution:

	def minimumNumberOfDeletions(self, S):
		S1 = S[::-1]
		r = ''
		grid = [[0 for i in range(len(S1) + 1)] for k in range(len(S) + 1)]
		for j in range(len(S1) - 1, -1, -1):
			for i in range(len(S) - 1, -1, -1):
				if S1[j] == S[i]:
					grid[i][j] = 1 + grid[i + 1][j + 1]
				else:
					grid[i][j] = max(grid[i + 1][j], grid[i][j + 1])
		return len(S) - grid[0][0]


class Solution:

	def dp_LPS_rev(self, m, n, X, Y):
		dp = [[0 for j in range(n + 1)] for i 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]:
					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 minimumNumberOfDeletions(self, s):
		n = len(s)
		return n - self.dp_LPS_rev(n, n, s, s[::-1])