Given string s and an integer, you have to transform s into a palindrome. In order to achieve that you have to perform exactly k insertion of characters(you cannot perform anymore or less number of insertions). The task is to check if the string can be converted to a palindrome by making exactly k insertions.
Example 1:
Input: s = "abac", K = 2
Output: 1
Explanation: "abac" can be transformed to 
"cabbac" (which is palindrome) adding 
two characters c and b.
Example 2:
Input: s = "abcde", K = 3
Output: 0
Explanation: "abcde" cannot be transformed
to palindrome using 3 insertions.
Your Task:  
You don't need to read input or print anything. Complete the function isPossiblePalindrome() which takes s and K as input parameters and returns a boolean value
Expected Time Complexity: O(|s|^{2})
Expected Auxiliary Space: O(|s|^{2})
Constraints:
1 ≤ |s| ≤ 103
s contains lower case English alphabets

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def isPossiblePalindrome(self, s, K):
		# code here

Solutions:
class Solution:

	def isPossiblePalindrome(self, s, K):
		n = len(s)
		s1 = s
		s2 = s[::-1]
		t = [[0 for _ 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]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return 1 if n - t[-1][-1] <= K else 0


class Solution:

	def isPossiblePalindrome(self, s, K):
		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
		c = dp[0][n - 1]
		if c <= K:
			return 1
		return 0


class Solution:

	def isPossiblePalindrome(self, a, K):
		b = a[::-1]
		n = len(a)
		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 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])
		inc = n - t[n][n]
		if inc <= K:
			return 1
		else:
			return 0


class Solution:

	def isPossiblePalindrome(self, s, K):
		rev = s[::-1]
		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][j + 1], dp[i + 1][j])
		x = dp[0][0]
		if n - x > K:
			return 0
		return 1


class Solution:

	def isPossiblePalindrome(self, s, K):
		s1 = s[:]
		s2 = s[::-1]
		x = self.lcs(s1, s2)
		if len(s) - x <= K:
			return 1
		else:
			return 0

	def lcs(self, s1, s2):
		x = len(s1)
		y = len(s2)
		dp = [[0 for _ in range(y + 1)] for __ 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 dp[-1][-1]


class Solution:

	def isPossiblePalindrome(self, s, K):
		dp = [[0 for i in range(len(s) + 1)] for j 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] == s[::-1][j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		if len(s) - dp[len(s)][len(s)] <= K:
			return 1
		else:
			return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		K = int(input())
		ob = Solution()
		ans = ob.isPossiblePalindrome(s, K)
		print(ans)


class Solution:

	def lcs(text1, text2, n):
		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 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[n][n]

	def isPossiblePalindrome(self, text, k):
		temp = len(text) - Solution.lcs(text, text[::-1], len(text))
		return 1 if temp <= k else 0


class Solution:

	def isPossiblePalindrome(self, s, K):
		if self.countMin(s) <= K:
			return 1
		return 0

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

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

	def lcs(self, x, y, s1, s2):
		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
				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[x][y]


class Solution:

	def isPossiblePalindrome(self, s, k):
		n = len(s)
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[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:
					dp[i][j] = 2
				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])
		return 1 if n - dp[0][n - 1] <= k else 0


class Solution:

	def isPossiblePalindrome(self, s1, K):
		s2 = s1[::-1]
		n = len(s1)
		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])
		if n - dp[n][n] <= K:
			return 1
		return 0