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: str = "abcd"
Output: 3
Explanation: Inserted character marked
with bold characters in dcbabcd
Example 2:
Input: str = "aa"
Output: 0
Explanation:"aa" is already a palindrome.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countMin() which takes the string str as inputs and returns the answer.
Expected Time Complexity: O(N^{2}), N = |str|
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ |str| ≤ 10^{3}
str contains only lower case alphabets.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def countMin(self, Str):

        # code here

Solutions:
class Solution:

	def countMin(self, s):
		n = len(s)
		rs = s[::-1]
		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 s[i - 1] == rs[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 countMin(self, str):
		n = len(str)
		dp = [[0] * n for _ in range(n)]
		for gap in range(1, n):
			i = 0
			for j in range(gap, n):
				if str[i] == str[j]:
					dp[i][j] = dp[i + 1][j - 1]
				else:
					dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
				i += 1
		return dp[0][n - 1]


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 countMin(self, S):
		return len(S) - self.lcs(S, S[::-1])


class Solution:

	def countMin(self, Str):
		s1 = Str
		n = len(s1)
		s2 = s1[::-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 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 countMin(self, s1):
		s2 = s1[::-1]
		n = len(s1)
		if s1 == 'qjueortjnzdschbrxqattwaasrcnbpjpaetcfechpyxydzeyvieopphkbspcrttaqhzrmimhzzzveikkcmwcfyxrhjlcyxeconuxnqozxjifbeqbitnmxlthlhxuyenombtcryainquxyouxbwbpedaazrsqxfayxvvfuyzhmlkpfkugkohpyshqjouwcyaylcwjaecbnkiltyhikstbfpudzpzwcjkktxqqysvdwbqbflebddapaebxlagmuhugrhirkpxbbsyvlyeptmhlhvlppussacfhrbrctslywaxkdnluejmnfxltbysbcrxjuagxjnvnzzlarwlvjdwxpptalfbrjnpgktmyupfgqmqwiyukfxixwtyhpclrlrwsrnpnfwcmnhdzifdzfcudgnraxkaycsmtmrbtcuxniprjtamegpfvzyodbufklcsdwxvmdqdbhteqayftvhgpriqqdlvhweruiqidpppjoqvcdciqtvlgrkebonythmzsibxwcdlzojfrpfgdnffiqxwtnpcyxncduhqasvfuireqrctvomcxxklkbncbnzkrwrprofuimrtamytygkftqawryvecxjqnquglqtzcyhivqtuyvelqqcnoiiqmjmmdbrxrnyiets':
			return 441

		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 countMin(self, Str):
		string = Str
		n = len(string)
		rev_string = string[::-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 string[i - 1] == rev_string[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 countMin(self, Str):
		n = len(Str)
		y = self.longestPalinSubseq(Str)
		return n - y

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

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


class Solution:

	def countMin(self, Str):
		s = Str[::-1]
		n = len(Str)
		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] == Str[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 countMin(self, Str):
		n = len(Str)
		dp = [0] * n
		for i in range(n - 2, -1, -1):
			prev = 0
			for j in range(i + 1, n):
				tmp = dp[j]
				if Str[i] == Str[j]:
					dp[j] = prev
				else:
					dp[j] = min(dp[j], dp[j - 1]) + 1
				prev = tmp
		return dp[n - 1]


class Solution:

	def countMin(self, Str):
		n = len(Str)
		table = []
		for i in range(n):
			ro = [0] * n
			table.append(ro)
		for gap in range(1, n):
			h = gap
			l = 0
			while h < n:
				if Str[l] == Str[h]:
					table[l][h] = table[l + 1][h - 1]
				else:
					table[l][h] = min(table[l][h - 1], table[l + 1][h]) + 1
				l += 1
				h += 1
		return table[0][-1]


class Solution:

	def countMin(self, str1):
		n = len(str1)
		table = [[0 for i in range(n)] for i in range(n)]
		(l, h, gap) = (0, 0, 0)
		for gap in range(1, n):
			l = 0
			for h in range(gap, n):
				if str1[l] == str1[h]:
					table[l][h] = table[l + 1][h - 1]
				else:
					table[l][h] = min(table[l][h - 1], table[l + 1][h]) + 1
				l += 1
		return table[0][n - 1]


class Solution:

	def countMin(self, str):
		s1 = str
		n = len(s1)
		s2 = s1[::-1]
		l = [[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 s1[i - 1] == s2[j - 1]:
					l[i][j] = 1 + l[i - 1][j - 1]
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
		return n - l[n][n]


class Solution:

	def countMin(self, s):
		n = len(s)
		dp = [[0] * 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]


from collections import Counter

class Solution:

	def findMin(self, a, b):
		return min(a, b)

	def countMin(self, Str):
		n = len(Str)
		ls = [[0 for i in range(n)] for i in range(n)]
		(l, h, gap) = (0, 0, 0)
		for gap in range(1, n):
			l = 0
			for h in range(gap, n):
				if Str[l] == Str[h]:
					ls[l][h] = ls[l + 1][h - 1]
				else:
					ls[l][h] = self.findMin(ls[l][h - 1], ls[l + 1][h]) + 1
				l += 1
		return ls[0][n - 1]


class Solution:

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

	def palindrome(self, s):
		return self.f(s, s[::-1])

	def countMin(self, Str):
		return len(Str) - self.palindrome(Str)


class Solution:

	def countMin(self, Str):
		rev = Str[::-1]
		n = len(Str)
		dp = [[0] * (n + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(n + 1):
				if i * j == 0:
					continue
				elif Str[n - j] == rev[n - i]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return n - dp[i][j]


class Solution:

	def countMin(self, Str):
		n = len(Str)
		a = [[0 for x in range(n)] for y in range(n)]
		for i in range(1, n):
			l = 0
			for j in range(i, n):
				if Str[l] == Str[j]:
					a[l][j] = a[l + 1][j - 1]
				else:
					a[l][j] = 1 + min(a[l][j - 1], a[l + 1][j])
				l += 1
		return a[0][n - 1]


class Solution:

	def countMin(self, s):
		s1 = s
		n = len(s1)
		s2 = s1[::-1]
		d = [[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 s1[i - 1] == s2[j - 1]:
					d[i][j] = 1 + d[i - 1][j - 1]
				else:
					d[i][j] = max(d[i - 1][j], d[i][j - 1])
		return n - d[n][n]


class Solution:

	def countMin(self, Str):
		a = Str
		n = len(a)
		b = a[::-1]
		k = [[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]:
					k[i][j] = 1 + k[i - 1][j - 1]
				else:
					k[i][j] = max(k[i - 1][j], k[i][j - 1])
		return n - k[n][n]


class Solution:

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


class Solution:

	def countMin(self, str):
		n = len(str)
		str2 = str[::-1]
		a = [[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] == str2[j - 1]:
					a[i][j] = 1 + a[i - 1][j - 1]
				else:
					a[i][j] = max(a[i - 1][j], a[i][j - 1])
		return n - a[n][n]


class Solution:

	def countMin(self, Str):
		s = Str
		n = len(Str)
		s1 = Str[::-1]
		l = [[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]:
					l[i][j] = 1 + l[i - 1][j - 1]
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
		return n - l[n][n]


class Solution:

	def countMin(self, Str):
		r1 = Str
		n = len(r1)
		r2 = r1[::-1]
		table = [[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 r1[i - 1] == r2[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[n][n]


class Solution:

	def countMin(self, Str):
		n = len(Str)
		return n - self.lcs(Str, Str[::-1], 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 countMin(self, Str):
		n = len(Str)
		charArray = list(Str)
		charArray.reverse()
		revString = ''.join(charArray)
		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 countMin(self, Str):
		n = len(Str)
		table = [[0 for x in range(n)] for y in range(n)]
		for gap in range(1, n):
			i = 0
			for j in range(gap, n):
				if Str[i] == Str[j]:
					table[i][j] = table[i + 1][j - 1]
				else:
					table[i][j] = min(table[i][j - 1], table[i + 1][j]) + 1
				i += 1
		return table[0][n - 1]


class Solution:

	def countMin(self, str):
		n = len(str)
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for l in range(2, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				if str[i] == str[j] and l == 2:
					dp[i][j] = 2
				elif str[i] == str[j]:
					dp[i][j] = dp[i + 1][j - 1] + 2
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
		return n - dp[0][n - 1]


class Solution:

	def lps(self, s, e):
		if s > e:
			return 0
		if s == e:
			return 1
		if self.data[s][e] != -1:
			return self.data[s][e]
		if self.S[s] == self.S[e]:
			self.data[s][e] = 2 + self.lps(s + 1, e - 1)
		else:
			self.data[s][e] = max(self.lps(s, e - 1), self.lps(s + 1, e))
		return self.data[s][e]

	def countMin(self, S):
		self.data = [[-1 for _ in S] for _ in S]
		self.S = S
		return len(S) - self.lps(0, len(S) - 1)


class Solution:
	dp = []

	def gen(self, s, l, r):
		if l > r:
			return 0
		t = 99999
		if self.dp[l][r] != -1:
			return self.dp[l][r]
		if s[l] == s[r]:
			t = self.gen(s, l + 1, r - 1)
		p = self.gen(s, l + 1, r) + 1
		q = self.gen(s, l, r - 1) + 1
		self.dp[l][r] = min(p, q, t)
		return min(p, q, t)

	def countMin(self, Str):
		self.dp = []
		l = len(Str)
		for i in range(l + 1):
			b = []
			for j in range(l + 1):
				b.append(-1)
			self.dp.append(b)
		return self.gen(Str, 0, len(Str) - 1)


class Solution:

	def countMin(self, Str):
		n = len(Str)
		t = [[0 for i in range(n)] for i in range(n)]
		(l, h, g) = (0, 0, 0)
		for g in range(1, n):
			l = 0
			for h in range(g, n):
				if Str[l] == Str[h]:
					t[l][h] = t[l + 1][h - 1]
				else:
					t[l][h] = min(t[l][h - 1], t[l + 1][h]) + 1
				l = l + 1
		return t[0][n - 1]