Given a string 'str' of size ‘n’. The task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome. Find the minimum numbers of characters we need to remove.
Note: The order of characters should be maintained.
Example 1:
Input: n = 7, str = "aebcbda"
Output: 2
Explanation: We'll remove 'e' and
'd' and the string become "abcba".
Ã¢â¬â¹Example 2:
Input: n = 3, str = "aba"
Output: 0
Explanation: We don't remove any
character.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minDeletions() which takes the string s and length of s as inputs and returns the answer.
Expected Time Complexity: O(|str|^{2})
Expected Auxiliary Space: O(|str|^{2})
Constraints:
1 ≤ |str| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3
class Solution:
    def minDeletions(self, Str, n): 
        #code here

Solutions:
class Solution:

	def minDeletions(self, Str, n):
		s1 = Str
		s2 = Str[::-1]
		n = len(s1)
		t = [[-1 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 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])
		x = t[n][n]
		return n - x


class Solution:

	def minDeletions(self, Str, n):
		s1 = Str
		s2 = Str[::-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:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[m][n]
		return m - lcs


class Solution:

	def lcs(self, s1: str, s2: str) -> int:
		(m, n) = (len(s1), len(s2))
		dp = [[0] * (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[-1][-1]

	def minDeletions(self, s, n):
		l = self.lcs(s, s[::-1])
		return n - l


class Solution:

	def largestPalindromicSubsequence(self, s):
		table = [[0 for x in range(len(s))] for y in range(len(s))]
		for i in range(len(s) - 1, -1, -1):
			table[i][i] = 1
			for j in range(i + 1, len(s)):
				if s[i] == s[j]:
					table[i][j] = 2 + table[i + 1][j - 1]
				else:
					table[i][j] = max(table[i + 1][j], table[i][j - 1])
		return table[0][len(s) - 1]

	def minDeletions(self, Str, n):
		return n - self.largestPalindromicSubsequence(Str)


class Solution:

	def minDeletions(self, Str, n):
		s2 = Str[::-1]
		x = n
		y = n
		T = [[0 for i in range(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 Str[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 len(Str) - T[x][y]


class Solution:

	def lcs(self, s1, s2, x, y):
		t = [[-1 for _ in range(y + 1)] for _ 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
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[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[x][y]

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


class Solution:

	def minDeletions(self, Str, n):
		if Str is None or n == 0:
			return 0
		arr = [[0] * n for _ in range(n)]
		for i in range(n):
			arr[i][i] = 1
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n):
				if Str[i] == Str[j]:
					arr[i][j] = 2 + arr[i + 1][j - 1]
				else:
					arr[i][j] = max(arr[i + 1][j], arr[i][j - 1])
		return n - arr[0][n - 1]


class Solution:

	def minDeletions(self, Str, n):
		tmp = Str[::-1]
		dp = [[0] * (n + 1) for i in range(n + 1)]
		if tmp == Str:
			return 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if Str[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 minDeletions(self, Str, n):
		temp = ''
		for i in range(n - 1, -1, -1):
			temp += Str[i]
		dp = [[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 or j == 0:
					dp[i][j] = 0
				elif Str[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 minDeletions(self, Str, n):
		s1 = Str
		s2 = Str[::-1]
		dp = [[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 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 n - dp[n][n]


class Solution:

	def minDeletions(self, Str, n):
		s = Str

		def lps():
			n = len(s)
			dp = [[0] * (n + 1) for _ in range(n + 1)]
			a = s
			b = s[::-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] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			return dp[-1][-1]
		return len(s) - lps()


class Solution:

	def minDeletions(self, s, n):
		memo = [[-1 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:
					memo[i][j] = 0
				elif s[i - 1] == rev_s[j - 1]:
					memo[i][j] = 1 + memo[i - 1][j - 1]
				else:
					memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
		max_len = memo[-1][-1]
		return n - max_len


class Solution:

	def minDeletions(self, Str, n):
		ans = self.longestPalindromeSubseq(Str)
		return n - ans

	def longestPalindromeSubseq(self, s):
		s1 = s
		input_str = s1[::-1]
		s2 = input_str
		ans = self.longestCommonSubsequence(s1, s2)
		return ans

	def longestCommonSubsequence(self, text1, text2):
		a = len(text1)
		b = len(text2)
		dp = [[0 for j in range(b + 1)] for i in range(a + 1)]
		return self.LCSutil(a, b, text1, text2, dp)

	def LCSutil(self, a, b, text1, text2, dp):
		for i in range(1, a + 1):
			for j in range(1, b + 1):
				if text1[i - 1] == text2[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[a][b]


class Solution:

	def minDeletions(self, Str, n):
		st1 = Str
		st2 = Str[::-1]
		m = len(st1)
		n = len(st2)
		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 st1[i - 1] == st2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		length = dp[m][n]
		return m - length


class Solution:

	def minDeletions(self, Str, n):
		s1 = Str
		s2 = Str[::-1]
		(x, y) = (n, n)
		subset = [[-1] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			subset[i][0] = 0
		for j in range(y + 1):
			subset[0][j] = 0
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					subset[i][j] = 1 + subset[i - 1][j - 1]
				else:
					subset[i][j] = max(subset[i - 1][j], subset[i][j - 1])
		return n - subset[x][y]


class Solution:

	def minDeletions(self, s, n):
		dp = [[0] * n for _ in range(n)]
		dp[0][0] = int(s[0] == s[-1])
		for i in range(1, n):
			if s[0] == s[-i - 1]:
				dp[0][i] = 1
			else:
				dp[0][i] = dp[0][i - 1]
			if s[i] == s[-1]:
				dp[i][0] = 1
			else:
				dp[i][0] = dp[i - 1][0]
		for i in range(1, n):
			for j in range(1, n):
				if s[i] == s[-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 n - dp[n - 1][n - 1]


class Solution:

	def minDeletions(self, Str, n):
		s2 = Str[::-1]
		m = n
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		ma = dp[0][0]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				x = i
				y = j
				if m == 0 or n == 0:
					dp[i][j] = 0
				elif Str[x - 1] == s2[y - 1]:
					dp[i][j] = 1 + dp[x - 1][y - 1]
				else:
					dp[i][j] = max(dp[x - 1][y], dp[x][y - 1])
		ans = dp[m][n]
		return n - ans


class Solution:

	def minDeletions(self, Str, n):

		def lps(S):

			def reverse(s):
				str = ''
				for i in s:
					str = i + str
				return str

			def lcs(x, y, s1, s2):
				T = [[0] * (y + 1) for i in range(x + 1)]
				for i in range(1, x + 1):
					for j in range(1, y + 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 T[x][y]
			return lcs(len(S), len(S), S, reverse(S))
		return len(Str) - lps(Str)


class Solution:

	def lcs(self, str1, str2):
		m = len(str1)
		n = len(str2)
		dp = [[-1] * (n + 1) for _ 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 str1[i - 1] == str2[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 minDeletions(self, Str, n):
		lcs = self.lcs(Str, Str[::-1])
		return len(Str) - lcs


class Solution:

	def minDeletions(self, Str, n):
		m = len(Str)
		Rtr = Str[::-1]
		t = [[-1 for j in range(m + 1)] for i in range(n + 1)]
		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 Str[i - 1] == Rtr[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][m]


class Solution:

	def minDeletions(self, Str, n):
		rev = Str[::-1]
		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 Str[i - 1] == 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 func(self, text1, text2, m, n, t):
		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 text1[i - 1] == text2[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]

	def lcs(self, text1: str, text2: str) -> int:
		n = len(text1)
		m = len(text2)
		t = [[0 for i in range(m + 1)] for i in range(n + 1)]
		c = self.func(text1, text2, n, m, t)
		return c

	def minDeletions(self, Str, n):
		s1 = Str[::-1]
		m = len(s1)
		c = self.lcs(Str, s1)
		return n - c


class Solution:

	def minDeletions(self, string, n):

		def longestPalindromeSubseq(s):

			def computeLCS(text1, text2):
				(m, n) = (len(text1), len(text2))
				dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
				for j in range(n + 1):
					dp[0][j] = 0
				for i in range(1, m + 1):
					dp[i][0] = 0
				for i in range(1, m + 1):
					for j in range(1, n + 1):
						(ch1, ch2) = (text1[i - 1], text2[j - 1])
						if ch1 == ch2:
							dp[i][j] = 1 + dp[i - 1][j - 1]
						else:
							dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
				return dp[m][n]
			(str1, str2) = (s, s[::-1])
			lps = computeLCS(str1, str2)
			return lps
		lps = longestPalindromeSubseq(string)
		ans = len(string) - lps
		return ans


class Solution:

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


class MiniDeletions(object):

	def __init__(self):
		pass

	def mini_deletions(self, text: str) -> int:
		text1 = text[:]
		text2 = text[::-1]
		num = self.lcomsubseq2(text1, text2)
		return len(text) - num

	def lcomsubseq(self, text1: str, text2: str) -> int:
		matrix = [[0] * (len(text2) + 1) for j in range(len(text1) + 1)]
		for i in range(1, len(text1) + 1):
			for j in range(1, len(text2) + 1):
				if text1[i - 1] == text2[j - 1]:
					matrix[i][j] = matrix[i - 1][j - 1] + 1
				else:
					matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])
		return matrix[len(text1)][len(text2)]

	def lcomsubseq2(self, text1: str, text2: str) -> int:
		matrix = [[0] * (len(text2) + 1) for i in range(2)]
		start = 0
		for i in range(len(text1)):
			for j in range(1, len(text2) + 1):
				if text1[i] == text2[j - 1]:
					matrix[start][j] = matrix[(start + 1) % 2][j - 1] + 1
				else:
					matrix[start][j] = max(matrix[start][j - 1], matrix[(start + 1) % 2][j])
			start ^= 1
		return matrix[(len(text1) + 1) % 2][len(text2)]

class Solution:

	def minDeletions(self, Str, n):
		minidel = MiniDeletions()
		return minidel.mini_deletions(Str)


class Solution:

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


class Solution:

	def minDeletions(self, Str, n):
		d = Str[::-1]
		t = [[0] * (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
				if i > 0 and j > 0:
					if Str[i - 1] == d[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 minDeletions(self, s, n):

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


class Solution:

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


class Solution:

	def minDeletions(self, Str, n):
		a = Str
		b = Str[::-1]
		n = len(a)
		temp = [[-1] * (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:
					temp[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if a[i - 1] == b[j - 1]:
					temp[i][j] = 1 + temp[i - 1][j - 1]
				else:
					temp[i][j] = max(temp[i - 1][j], temp[i][j - 1])
		return len(Str) - temp[n][n]


class Solution:

	def minDeletions(self, Str, n):
		dp = [[0] * n for i 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 Str[i] == Str[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 minDeletions(self, S, n):
		s1 = S[::-1]
		res = [[0 for _ in range(n + 1)] for x 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]:
					res[i][j] = 1 + res[i - 1][j - 1]
				else:
					res[i][j] = max(res[i - 1][j], res[i][j - 1])
		return n - res[n][n]


class Solution:

	def minDeletions(self, Str, n):
		l = len(Str)
		orig = Str
		rev = Str[::-1]
		dp = [[0 for x in range(l + 1)] for x in range(l + 1)]
		for i in range(l + 1):
			for j in range(l + 1):
				if i * j == 0:
					dp[i][j] = 0
		for i in range(1, l + 1):
			for j in range(1, l + 1):
				ind1 = i - 1
				ind2 = j - 1
				if orig[ind1] == rev[ind2]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return l - dp[l][l]


class Solution:

	def minDeletions(self, str, n):
		s2 = str[::-1]
		t = [[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 str[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 n - t[n][n]


class Solution:

	def minDeletions(self, S, n):
		t = S[::-1]
		dp = [[0] * (n + 1) for i in range(n + 1)]
		for i in range(0, n + 1):
			for j in range(0, n + 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 minDeletions(self, X, n):
		table = [[-1] * (n + 1) for _ in range(n + 1)]
		Y = X[::-1]
		for i in range(n + 1):
			table[i][0] = 0
			table[0][i] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[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 n - table[-1][-1]


class Solution:

	def minDeletions(self, Str, n):
		r = Str[::-1]
		l1 = len(Str)
		l2 = len(r)
		dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
		for i in range(l1 + 1):
			for j in range(l2 + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if Str[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 minDeletions(self, Str, n):

		def lps(str1, str2, m):
			dp = [[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 str1[i - 1] == str2[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][m]
		return n - lps(Str, Str[::-1], n)


class Solution:

	def minDeletions(self, Str, n):
		S = Str
		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 n - ans


class Solution:

	def minDeletions(self, S, n):
		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 minDeletions(self, Str, n):
		DP = [[0 for i in range(n)] for j in range(n)]
		for i in range(n - 1, -1, -1):
			DP[i][i] = 1
			for j in range(i + 1, n):
				if Str[i] == Str[j]:
					DP[i][j] = 2 + DP[i + 1][j - 1]
				else:
					DP[i][j] = max(DP[i + 1][j], DP[i][j - 1])
		return n - DP[0][-1]


class Solution:

	def lcs(self, a, b, 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 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 t[m][n]

	def minDeletions(self, Str, n):
		s = Str[::-1]
		a = self.lcs(Str, s, n, n)
		return n - a


class Solution:

	def minDeletions(self, Str, n):
		opt = [[0 for _ in range(n)] for _ in range(n)]
		min_deletions = 0
		for i in range(n):
			opt[i][i] = 1
		for i in range(n - 1, -1, -1):
			for j in range(i + 1, n):
				if Str[i] == Str[j]:
					opt[i][j] = 2 + opt[i + 1][j - 1]
				else:
					opt[i][j] = max(opt[i + 1][j], opt[i][j - 1])
		lps = opt[0][n - 1]
		min_deletions = n - lps
		return min_deletions


class Solution:

	def minDeletions(self, strg, n):
		dp = []
		for i in range(n + 1):
			dp.append([-1] * (n + 1))
		rev = strg[::-1]
		for i in range(n + 1):
			dp[0][i] = 0
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if strg[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 n - dp[n][n]


class Solution:

	def minDeletions(self, Str, n):
		return n - self.sub(Str)

	def sub(self, s):
		dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
		for row in range(1, len(s) + 1):
			for col in range(1, len(s) + 1):
				temp_text1 = s[row - 1]
				temp_text2 = s[len(s) - col]
				if temp_text1 == temp_text2:
					dp[row][col] = 1 + dp[row - 1][col - 1]
				else:
					dp[row][col] = max(dp[row - 1][col], dp[row][col - 1])
		return dp[-1][-1]


class Solution:

	def minDeletions(self, s, n):
		y = s[::-1]
		t = [[0] * (n + 1) for k in range(n + 1)]
		m = 0
		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 minDeletions(self, Str, n):
		count = 0
		b = Str[::-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 Str[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])
		res = dp[-1][-1]
		return n - res


class Solution:

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

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


class Solution:

	def minDeletions(self, Str, n):

		def lcs(s, t):
			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] == 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]
		s = Str
		t = s[::-1]
		return n - lcs(s, t)


class Solution:

	def minDeletions(self, Str, n):
		seq1 = Str
		seq2 = Str[::-1]
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if seq1[i - 1] == seq2[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 minDeletions(self, Str, n):
		s = Str
		x = y = len(s)
		s1 = s
		s2 = s[::-1]
		dp = [[-1 for j in range(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
				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])
		lps = dp[x][y]
		return x - lps


class Solution:

	def minDeletions(self, Str, n):
		seq1 = Str
		seq2 = Str[::-1]
		idx1 = n
		idx2 = n

		def lcs(seq1, seq2, idx1, idx2):
			dp = [[0] * (n + 1) for _ in range(n + 1)]
			for i in range(1, n + 1):
				for j in range(1, n + 1):
					if seq1[i - 1] == seq2[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]
		a = lcs(seq1, seq2, idx1, idx2)
		return n - a


class Solution:

	def minDeletions(self, Str, n):
		Str1 = Str[::-1]
		m = len(Str)
		n = len(Str1)
		t = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if Str[i - 1] == Str1[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[m][n]


class Solution:

	def solve(self, a: str, b: str):
		(n1, n2) = (len(a), len(b))
		dp = [[0] * (n2 + 1) for i in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if 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[n1][n2]

	def minDeletions(self, Str, n):
		b = Str[::-1]
		return n - self.solve(Str, b)


class Solution:

	def minDeletions(self, str1, l1):
		str2 = str1[::-1]
		l2 = l1
		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 lcs(self, s1, s2, m, n):
		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 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 minDeletions(self, S, n):
		rev = S[::-1]
		val = self.lcs(S, rev, n, n)
		return n - val


class Solution:

	def minDeletions(self, s1, n):
		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 minDeletions(self, s, n):
		rev_s = s[::-1]
		m = len(s)
		n = len(rev_s)
		dp = [[0] * (n + 1) for _ in range(m + 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] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return m - dp[m][n]


class Solution:

	def minDeletions(self, x, m):
		y = x[::-1]
		n = len(y)
		T = [[0 for _ in range(n + 1)] for _ 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][j - 1], T[i - 1][j])
		lps_len = T[m][n]
		return m - lps_len


class Solution:

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


class Solution:

	def minDeletions(self, Str, n):
		rev = ''.join(reversed(Str))
		t = [[-1 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 or j == 0:
					t[i][j] = 0
				elif Str[i - 1] == 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[-1][-1]