Given a string str of length n, find if the string is K-Palindrome or not. A k-palindrome string transforms into a palindrome on removing at most k characters from it.
Example 1:
Input: str = "abcdecba"
n = 8, k = 1
Output: 1
Explaination: By removing 'd' or 'e' 
we can make it a palindrome.
Example 2:
Input: str = "abcdefcba"
n = 9, k = 1
Output: 0
Explaination: By removing a single 
character we cannot make it a palindrome.
Your Task:
You do not need to read input or print anything. Your task is to complete the function kPalindrome() which takes string str, n and k as input parameters and returns 1 if str is a K-palindrome else returns 0.
Expected Time Complexity: O(n*n)
Expected Auxiliary Space: O(n*n)
Constraints:
1 ≤ n, k ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def kPalindrome(self, str, n, k):
        # code here

Solutions:
class Solution:

	def kPalindrome(self, str, n, k):

		def isKPalDP(str1, str2, m, n):
			dp = [[0] * (n + 1) for _ in range(m + 1)]
			for i in range(m + 1):
				for j in range(n + 1):
					if not i:
						dp[i][j] = j
					elif not j:
						dp[i][j] = i
					elif str1[i - 1] == str2[j - 1]:
						dp[i][j] = dp[i - 1][j - 1]
					else:
						dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
			return dp[m][n]
		rev = str[::-1]
		return 1 if isKPalDP(str, rev, n, n) <= 2 * k else 0


class Solution:

	def kPalindrome(self, str, n, k):
		n1 = str[::-1]
		dp = [[None 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
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if n1[i - 1] == str[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
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, k):
		if n == 1:
			return 1
		n2 = 9999
		while n2 > n:
			n2 = n
			if str[0] == str[-1]:
				str = str.replace(str[0], '', 1)
				str = str.replace(str[-1], '', 1)
			n = len(str)
		if n - k <= 1:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, k):
		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 int(dp[0][n - 1] <= k)


class Solution:

	def kPalindrome(self, str, n, k):
		S = str
		n = len(S)
		dp = [[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]:
					dp[l][h] = dp[l + 1][h - 1]
				else:
					dp[l][h] = min(dp[l + 1][h], dp[l][h - 1]) + 1
				l = l + 1
		if dp[0][n - 1] <= k:
			return 1
		return 0


class Solution:

	def kPalindrome(self, string, n, k):
		return self.helper(string, n, k, {})

	def helper(self, string, n, k, store):
		if string in store:
			return store[string]
		if k == 0:
			store[string] = int(string == string[::-1])
			return store[string]
		if n < 2:
			return 1
		if string[0] == string[-1]:
			store[string] = self.helper(string[1:-1], n - 2, k, store)
			return store[string]
		if self.helper(string[1:], n - 1, k - 1, store):
			store[string] = 1
			return 1
		if self.helper(string[:-1], n - 1, k - 1, store):
			store[string] = 1
			return 1
		store[string] = 0
		return 0


class Solution:

	def kPalindrome(self, str, n, k):
		min_deletions = 0
		opt = [[0 for _ in range(n)] for _ in range(n)]
		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
		if min_deletions <= k:
			return 1
		return 0


class Solution:

	def kPalindrome(self, str, n, k):
		rev = str[::-1]
		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 str[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])
		count = dp[0][0]
		change = n - count
		if change <= k:
			return 1
		return 0


class Solution:

	def kPalindrome(self, str, n, k):
		k_palindrome = False
		rev = str[::-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 str[i - 1] == rev[j - 1]:
					d[i][j] = d[i - 1][j - 1] + 1
				else:
					d[i][j] = max(d[i - 1][j], d[i][j - 1])
		k_palindrome = n - d[n][n] <= k
		if k_palindrome:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, K):
		if n - K <= 1:
			return 1
		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 str[i + k] == str[k]:
					dp[k][i + k] = dp[k + 1][i + k - 1] + 2
				else:
					dp[k][i + k] = max(dp[k + 1][i + k], dp[k][i + k - 1])
		min_k = n - dp[0][n - 1]


class Solution:

	def kPalindrome(self, Str, n, k):
		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])
		if n - l[n][n] <= k:
			return 1
		return 0


class Solution:

	def kPalindrome(self, str, n, k):
		k_palindrome = 0
		reverse_string = str[::-1]
		l = len(str)
		dp = [[0] * (l + 1) for _ in range(l + 1)]
		for i in range(l + 1):
			for j in range(l + 1):
				if not i:
					dp[i][j] = j
				elif not j:
					dp[i][j] = i
				elif str[i - 1] == reverse_string[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
		if dp[l][l] <= k * 2:
			return 1
		return k_palindrome


class Solution:

	def kPalindrome(self, Str, n, k):
		s1 = Str
		s2 = Str[::-1]
		dp = [[0 for i in range(len(s1) + 1)] for i in range(len(s2) + 1)]
		for i in range(1, len(s2) + 1):
			for j in range(1, len(s1) + 1):
				if s2[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])
		lcss = dp[-1][-1]
		return 1 if len(s1) - lcss <= k else 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 min_number_of_removals_of_to_make_a_string_palindrome(self, n, s):
		return n - self.dp_LPS_rev(n, n, s, s[::-1])

	def kPalindrome(self, s, n, k):
		if self.min_number_of_removals_of_to_make_a_string_palindrome(n, s) > k:
			return 0
		return 1


class Solution:

	def kPalindrome(self, S, n, k):
		rev = ''
		for i in S:
			rev = i + rev

		def lcs(S, rev, n):
			mat = [[0] * (n + 1) for _ in range(n + 1)]
			for i in range(1, n + 1):
				for j in range(1, n + 1):
					if S[i - 1] == rev[j - 1]:
						mat[i][j] = mat[i - 1][j - 1] + 1
					else:
						mat[i][j] = max(mat[i][j - 1], mat[i - 1][j])
			return mat[-1][-1]
		v = lcs(S, rev, n)
		if k >= n - v:
			return 1
		return 0


class Solution:

	def kPalindrome(self, str, n, k):

		def recur(s, i, j, k):
			if i == j:
				return 1
			if k < 0:
				return 0
			if s[i] != s[j]:
				if k == 0:
					return 0
				return recur(s, i + 1, j, k - 1) or recur(s, i, j - 1, k - 1)
			else:
				return recur(s, i + 1, j - 1, k)

		def memoize(s, i, j, k, dp):
			if (i, j, k) in dp:
				return dp[i, j, k]
			if i == j:
				return 1
			if k < 0:
				return 0
			if s[i] != s[j]:
				if k == 0:
					return 0
				dp[i, j, k] = memoize(s, i + 1, j, k - 1, dp) or memoize(s, i, j - 1, k - 1, dp)
			else:
				dp[i, j, k] = memoize(s, i + 1, j - 1, k, dp)
			return dp[i, j, k]
		return memoize(str, 0, n - 1, k, {})


class Solution:

	def kPalindrome(self, str, n, k):

		def lcs(str):
			n = len(str)
			s1 = str[::-1]
			dp = [[0] * (n + 1) for _ in range(n + 1)]
			for i in range(n):
				for j in range(n):
					if str[i] == s1[j]:
						dp[i + 1][j + 1] = 1 + dp[i][j]
					else:
						dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
			return dp[-1][-1]
		return 1 if lcs(str) >= n - k else 0


class Solution:

	def kPalindrome(self, s, n, k):
		memo = {}

		def rec(string, deletions):
			if deletions > k:
				return 0
			if string == string[::-1]:
				return 1
			if (string, deletions) in memo:
				return memo[string, deletions]
			ans = 0
			if string[0] == string[-1]:
				ans = rec(string[1:-1], deletions)
			else:
				ans = rec(string[1:], deletions + 1) or rec(string[:-1], deletions + 1)
			memo[string, deletions] = ans
			return ans
		return rec(s, 0)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		n = int(arr[0])
		k = int(arr[1])
		str = input()
		ob = Solution()
		print(ob.kPalindrome(str, n, k))


class Solution:

	def kPalindrome(self, s, n, k):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = i + g
			while j < n:
				if g == 0:
					dp[i][j] = 1
				elif g == 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 int(n - dp[0][-1] <= k)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		n = int(arr[0])
		k = int(arr[1])
		str = input()
		ob = Solution()
		print(ob.kPalindrome(str, n, k))


class Solution:

	def kPalindrome(self, s, n, k):
		rev = s[::-1]
		dp = []
		for i in range(n + 1):
			ls = [-1] * (n + 1)
			dp.append(ls)
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(n + 1):
			dp[0][i] = 0
		for i in range(1, n + 1):
			for j in range(1, n + 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])
		deletion = n - dp[n][n]
		if deletion <= k:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		n = int(arr[0])
		k = int(arr[1])
		str = input()
		ob = Solution()
		print(ob.kPalindrome(str, n, k))


class Solution:

	def kPalindrome(self, str, n, k):
		rev = ''
		for c in str:
			rev = c + rev

		def longestpalindrome(a, b, n):
			dp = [[0] * (n + 1) for i in range(n + 1)]
			for i in range(n + 1):
				for j in range(n + 1):
					if not i:
						dp[i][j] = 0
					elif not j:
						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][j - 1], dp[i - 1][j])
			return dp[-1][-1]
		length = longestpalindrome(str, rev, len(rev))
		if len(rev) - length <= k:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		n = int(arr[0])
		k = int(arr[1])
		str = input()
		ob = Solution()
		print(ob.kPalindrome(str, n, k))


class Solution:

	def kPalindrome(self, string, n, k):

		def lcs(s1, s2, n):
			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 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][n]
		ans = lcs(string, string[::-1], len(string))
		if len(string) - ans <= k:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, s, n, k):
		s2 = s[::-1]
		n = len(s)
		dp = [[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] == s2[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 n - dp[n][n] <= k:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, k):
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[i][0] = 1
		for j in range(n):
			dp[0][j] = 1
		rstr = str[::-1]
		for i in range(1, n):
			for j in range(1, n):
				if rstr[i] == str[j]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		if n - dp[n - 1][n - 1] <= k:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, k):
		Str1 = str
		Str2 = str[::-1]
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = i
		for j in range(n + 1):
			dp[0][j] = j
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if Str1[i - 1] == Str2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
		if dp[n][n] <= 2 * k:
			return 1
		else:
			return 0


class Solution:

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


class Solution:

	def kPalindrome(self, str, n, k):
		l = 0
		r = n - 1
		while r >= l:
			if str[l] != str[r]:
				if k > 0:
					k -= 1
					if str[l] == str[r - 1]:
						l -= 1
					else:
						r += 1
				else:
					return 0
			l += 1
			r -= 1
		return 1


class Solution:

	def kPalindrome(self, a, n, k):
		i = 0
		j = n - 1
		while i < j:
			if a[i] != a[j]:
				if a[i] == a[j - 1]:
					i -= 1
				else:
					j += 1
				k -= 1
			i += 1
			j -= 1
		if k >= 0:
			return 1
		return 0


class Solution:

	def kPalindrome(self, str, n, k):
		from functools import lru_cache

		@lru_cache(None)
		def valid(lo, hi, k):
			if k < 0:
				return False
			if lo >= hi:
				return True
			if str[lo] == str[hi]:
				return valid(lo + 1, hi - 1, k)
			else:
				return valid(lo, hi - 1, k - 1) or valid(lo + 1, hi, k - 1)
		return 1 if valid(0, len(str) - 1, k) else 0


class Solution:

	def kPalindrome(self, s, n, c):
		memo = {}

		def ispalindrome(l, r, deletes):
			if (l, r, deletes) in memo:
				return memo[l, r, deletes]
			if deletes > c:
				return False
			if l > r:
				return True
			best = ispalindrome(l + 1, r - 1, deletes) if s[l] == s[r] else ispalindrome(l, r - 1, deletes + 1) or ispalindrome(l + 1, r, deletes + 1)
			memo[l, r, deletes] = best
			return best
		N = len(s)
		if ispalindrome(0, N - 1, 0):
			return 1
		return 0


class Solution:

	def kPalindrome(self, s, n, k):
		if n == 1 or k > n:
			return 1
		count = 0
		if n % 2 == 0:
			k += 1
		for i in range(n):
			if s[i] != s[n - (i + 1)]:
				count += 1
		if count == k:
			return 1
		else:
			return 0


class Solution:

	def kPalindrome(self, str, n, k):
		a = str
		b = str[::-1]
		c = 0
		for i in range(n):
			if a[i] != b[i]:
				if n % 2 == 0 and i == n // 2:
					c -= 1
				c += 1
		if c > k:
			return 0
		return 1