You are given a binary string S and an integer K. In one operation, you can pick any bit and flip it, i.e turn 0 to 1 or 1 to 0. Can you make the string S a [palindrome] using exactly K operations?

Print YES if this is possible, and NO if it is not.

------ Input Format ------ 

- The first line of input contains one integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains two space-separated integers N and K, denoting the length of the binary string and the number of operations to be performed.
- The second line contains the binary string S.

------ Output Format ------ 

For each test case, print the answer on a new line — YES if the S can be made a palindrome using exactly K operations, and NO otherwise.

You may print each character of YES and NO in either uppercase or lowercase (for example, yes, yEs, Yes will all be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 1000$
$0 ≤ K ≤ N$
$S$ is a binary string, i.e, contains only characters $0$ and $1$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
3 0
110
6 1
101100

----- Sample Output 1 ------ 
NO
YES

----- explanation 1 ------ 
Test case $1$: $S$ is not a palindrome, and no operations can be performed on it because $K = 0$.

Test case $2$: Flip the first bit to obtain $S = 001100$, which is a palindrome.

Difficulty: MEDIUM
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	s = input()
	d = s[::-1]
	a = 0
	for i in range(n):
		if s[i] != d[i]:
			a += 1
	a //= 2
	if a > k or (n % 2 == 0 and (a - k) % 2 == 1):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		print('YES')
		continue
	for i in range(n // 2):
		if s[i] != s[-(i + 1)]:
			k -= 1
	if k >= 0:
		if n & 1:
			print('YES')
		elif k & 1:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	b = input().strip()
	poss = True
	mid = n // 2
	c = 0
	for i in range(mid):
		if b[i] != b[n - 1 - i]:
			c += 1
	if c > k:
		poss = False
	if n % 2 == 0:
		diff = k - c
		if diff % 2 != 0:
			poss = False
	print('YES' if poss else 'NO')


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	s = input()
	c = 0
	j = 0
	k = n - 1
	while j < k:
		if s[j] != s[k]:
			c += 1
		j += 1
		k -= 1
	if c <= x:
		if n & 1 == 1:
			print('YES')
		elif (x - c) % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif n == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	for i in range(0, n // 2):
		if s[i] != s[n - 1 - i]:
			k -= 1
	if k >= 0:
		if n % 2 == 1:
			print('YES')
		elif k % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')
	t -= 1


c = int(input())
l = []
for im in range(0, c):
	kl = str(input())
	kl = kl.split(' ')
	lp = int(kl[-1])
	mm = str(input())
	ume = [lp, mm]
	l.append(ume)
for tt in l:
	umthj = tt[0]
	a = tt[1]
	x = 0
	if len(a) % 2 == 0:
		x = len(a) // 2
	else:
		x = (len(a) + 1) // 2
	pdfr = list(a)
	for jk in range(0, x):
		if a[jk] != a[len(a) - jk - 1]:
			pdfr.pop(jk)
			pdfr.insert(jk, a[len(a) - jk - 1])
			umthj -= 1
	gbt = ''.join(pdfr)
	if umthj == 0:
		print('YES')
	elif umthj < 0:
		print('NO')
	else:
		e = 0
		for unb in range(0, x):
			if unb != len(a) - unb - 1:
				ap = umthj
				ap -= 2
				if ap < 0:
					continue
				if ap == 0:
					e = 1
					break
				else:
					umthj -= 2
			else:
				ap = umthj
				ap -= 1
				if ap < 0:
					continue
				elif ap == 0:
					e = 1
					break
				else:
					umthj -= 1
		if e == 1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(n, z) = map(int, input().split())
	st = input()
	count1 = 0
	j = 0
	k = n - 1
	while j < k:
		if st[j] != st[k]:
			count1 += 1
		j += 1
		k -= 1
	if count1 == z:
		print('YES')
	elif n == 1:
		print('YES')
	elif n % 2 != 0 and z > count1:
		print('YES')
	elif n % 2 == 0 and (z - count1) % 2 == 0 and (z > count1):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	string = str(input())
	count = 0
	if n == 1:
		print('YES')
	else:
		for x in range(0, n // 2):
			if string[x] != string[n - x - 1]:
				count += 1
		if k == 0 and count > 0:
			print('NO')
		elif count <= k:
			if n & 1 == 1:
				print('YES')
			elif (k - count) % 2 == 0:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = list(input())
	c = 0
	for i in range(a // 2):
		if n[i] != n[-(i + 1)]:
			c += 1
	if b == 0 and c > 0:
		print('NO')
	elif c <= b:
		if a % 2 == 1:
			print('YES')
		elif (c - b) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	left = 0
	right = n - 1
	res = 0
	while left < right:
		if s[left] != s[right]:
			res += 1
		left += 1
		right -= 1
	if res > k:
		print('NO')
	elif res <= k and n % 2 != 0:
		print('YES')
	elif res <= k and n % 2 == 0 and ((k - res) % 2 == 0):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(N, K) = map(int, input().split(' '))
	st = input()
	l = 0
	k = 0
	for j in range(N // 2):
		if st[j] != st[N - j - 1]:
			l += 1
	if l == K or N - l == K:
		print('YES')
	elif N % 2 == 0 and K >= l and ((K - l) % 2 == 0):
		print('YES')
	elif N % 2 == 1 and K > l:
		print('YES')
	else:
		print('NO')


mapinput = lambda : map(int, input().split(' '))
for _ in range(int(input())):
	(n, k) = mapinput()
	B = input()
	c = 0
	for i in range(n // 2):
		if B[i] != B[n - i - 1]:
			k -= 1
	if k == 0 or (k > 0 and (k % 2 == 0 or n % 2 == 1)):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	bin_str = input()
	for i in range(int(N / 2)):
		if bin_str[i] == '0' and bin_str[N - 1 - i] == '1':
			K -= 1
		elif bin_str[i] == '1' and bin_str[N - 1 - i] == '0':
			K -= 1
	if N % 2 != 0:
		if K >= 0:
			print('YES')
		else:
			print('NO')
	elif K >= 0 and K % 2 == 0:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	(num, k) = map(int, input().split())
	s = input()
	c = 0
	for i in range(num // 2):
		if s[i] != s[num - i - 1]:
			c += 1
	if c > k:
		print('NO')
	elif num % 2 or (num % 2 == 0 and (k - c) % 2 == 0):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			count += 1
	if count > k:
		print('NO')
	elif n % 2 or (n % 2 == 0 and (k - count) % 2 == 0):
		print('YES')
	else:
		print('NO')


T = int(input())
for x in range(T):
	(n, k) = map(int, input().split())
	s = input()
	a = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			a += 1
	if a > k:
		print('NO')
	elif n % 2 or (n % 2 == 0 and (k - a) % 2 == 0):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	k = list(input())
	a = 0
	for j in range(x // 2):
		if k[j] != k[x - 1 - j]:
			a += 1
	if y == 0 and a > 0:
		print('NO')
	elif a <= y:
		if x % 2 == 1:
			print('YES')
		elif (y - a) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	string = input()
	for j in range(n // 2):
		if string[j] != string[-j - 1]:
			k -= 1
	if k == 0 or (k > 0 and (n & 1 or k % 2 == 0)):
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	count = 0
	reverse = s[::-1]
	for i in range(n // 2):
		if s[i] != reverse[i]:
			count += 1
	if count <= k:
		if n % 2 != 0 or (k - count) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	left = 0
	right = n - 1
	flip = 0
	x = k
	while left < right:
		if s[left] != s[right]:
			flip += 1
		left += 1
		right -= 1
	if k < flip:
		print('NO')
	else:
		x = flip - k
		if x % 2 == 0:
			print('YES')
		elif n % 2 == 1:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	s1 = input()
	count = 0
	for i in range(n // 2):
		if s1[i] != s1[n - i - 1]:
			count += 1
	if k >= count:
		if n % 2 != 0 or (k - count) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for i in range(int(input())):
	t = 0
	(x, y) = map(int, input().split())
	z = list(map(int, input().strip()))
	for j in range(x // 2):
		if z[j] != z[x - 1 - j]:
			t = t + 1
	c = y - t
	if c >= 0 and c % 2 == 0 or (c >= 0 and x % 2 == 1):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	lst = list(map(int, input().split()))
	(n, k) = (lst[0], lst[1])
	string = input()
	rev = string[::-1]
	for i in range(n // 2):
		if rev[i] != string[i]:
			k -= 1
	if k == 0 or ((k % 2 == 0 or n % 2 == 1) and k > 0):
		print('YES')
	else:
		print('NO')


t = int(input())
l = []
for x in range(t):
	a = input()
	l = a.split(' ')
	k = int(l[0])
	z = int(l[1])
	s = input()
	count = 0
	for i in range(int(k / 2)):
		if s[i] != s[k - i - 1]:
			count = count + 1
	if count > z:
		print('NO')
	elif k % 2 or (k % 2 == 0 and (z - count) % 2 == 0):
		print('YES')
	else:
		print('NO')


t = int(input())
for x in range(t):
	(n, k) = [int(d) for d in input().split()]
	s = input()
	sr = s[::-1]
	count = 0
	for i in range(n // 2):
		if s[i] != sr[i]:
			count += 1
	if k >= count:
		if n % 2 != 0:
			print('YES')
		elif (k - count) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if len(s) == 1:
		print('YES')
	else:
		first = 0
		last = len(s) - 1
		c = 0
		while first < last:
			if s[first] != s[last]:
				c += 1
			first += 1
			last -= 1
		if c > k:
			print('NO')
		elif (k - c) % 2 == 0:
			print('YES')
		elif len(s) % 2 != 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	if n == 1:
		print('YES')
	else:
		a1 = list(a)
		s1 = a[:n // 2]
		s2 = a[n // 2:]
		if n % 2 == 1:
			s2 = a[n // 2 + 1:]
		rs2 = s2[::-1]
		c = 0
		for i in range(n // 2):
			if s1[i] != rs2[i]:
				c += 1
		if n % 2 == 1:
			if k >= c:
				print('YES')
			else:
				print('NO')
		elif k >= c and (k - c) % 2 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = str(input())
	l = [i for i in S]
	flag = 1
	v = 0
	for i in range(N // 2):
		if l[i] != l[-i - 1]:
			v += 1
	if K >= v:
		if N % 2 != 0:
			print('YES')
		elif (K - v) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	s = input()
	x = 0
	for i in range(0, a // 2):
		if s[i] != s[a - 1 - i]:
			x += 1
	if a % 2 == 0:
		if a == 1:
			print('YES')
		elif x == b:
			print('YES')
		elif x < b and (b - x) % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif a == 1:
		print('YES')
	elif x <= b:
		print('YES')
	else:
		print('NO')


def get(s):
	n = len(s)
	k = 0
	for i in range(n // 2):
		if s[i] != s[n - 1 - i]:
			k += 1
	return k
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = get(s)
	if n % 2 == 1 and k >= d or (n % 2 == 0 and k >= d and ((k - d) % 2 == 0)):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(0, T):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	st = input()
	st = list(st)
	sums = 0
	for j in range(0, a // 2):
		if st[j] != st[j * -1 - 1]:
			sums += 1
	if a == 1:
		print('YES')
	elif a % 2 == 1 and b >= sums:
		print('YES')
	elif a % 2 == 1 and b < sums:
		print('NO')
	elif a % 2 == 0:
		if b < sums:
			print('NO')
		elif b == sums:
			print('YES')
		elif (b - sums) % 2 == 0:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n < 2:
		print('YES')
		continue
	if n % 2 == 0:
		mid_i = n // 2 - 1
		mid_j = n // 2
	else:
		if s == s[::-1]:
			if k == 1:
				print('YES')
				continue
		mid_i = n // 2 - 1
		mid_j = n // 2 + 1
	cnt = 0
	while mid_i >= 0 and mid_j < n:
		if s[mid_i] != s[mid_j]:
			cnt += 1
		mid_i -= 1
		mid_j += 1
	if cnt > k:
		print('NO')
	elif cnt == k:
		print('YES')
	else:
		val = k - cnt
		if val % 2 == 0:
			print('YES')
		elif n % 2 == 1:
			print('YES')
		else:
			print('NO')


a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	s = list(input())
	c = 0
	for j in range(n // 2):
		if s[j] != s[n - 1 - j]:
			c = c + 1
	if c <= k:
		if n % 2 == 1:
			print('YES')
		elif (k - c) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	x1 = s[:n // 2]
	x2 = s[:-(n + 1) // 2:-1]
	t = sum((a != b for (a, b) in zip(x1, x2)))
	print('NO' if k < t or (n % 2 == 0 and k % 2 != t % 2) else 'YES')


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	k -= sum((s[i] != s[n - i - 1] for i in range(n // 2)))
	if k >= 0 and (k % 2 == 1 and n % 2 == 1 or k % 2 == 0):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = str(input())
	(lo, hi) = (0, n - 1)
	cnt = 0
	if n == 1:
		print('YES')
	else:
		while lo <= hi:
			if s[lo] != s[hi]:
				cnt += 1
			lo += 1
			hi -= 1
		if cnt > k:
			print('NO')
		elif cnt == k:
			print('YES')
		else:
			x = k - cnt
			if n % 2 != 0:
				print('YES')
			elif x % 2 == 0:
				print('YES')
			else:
				print('NO')


T = int(input())
for i in range(T):
	(s, k) = map(int, input().split())
	string = input()
	left = 0
	right = s - 1
	not_matching = 0
	while right > left:
		if string[left] != string[right]:
			not_matching += 1
			left += 1
			right -= 1
		else:
			left += 1
			right -= 1
	if s % 2:
		if not_matching <= k:
			print('YES')
		else:
			print('NO')
	elif not_matching <= k and (k - not_matching) % 2 == 0:
		print('YES')
	else:
		print('NO')


def fun():
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			c += 1
	k -= c
	if k >= 0 and k % 2 == 0:
		print('YES')
		return
	elif k >= 0 and k % 2 == 1 and (n % 2 == 1):
		print('YES')
		return
	print('NO')
t = int(input())
for _ in range(t):
	fun()


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	(n, k) = map(int, stdin.readline().strip().split(' '))
	s = stdin.readline().strip()[:n]
	j = n - 1
	i = 0
	op = 0
	while i < j:
		if s[i] != s[j]:
			op += 1
		i += 1
		j -= 1
	if op <= k:
		if n % 2 == 1:
			print('YES')
		elif (k - op) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	binary = input()
	for i in range(n // 2):
		if binary[i] != binary[n - i - 1]:
			k -= 1
	if k < 0:
		print('NO')
		continue
	if n & 1:
		print('YES')
		continue
	if not k & 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	if n % 2 == 0:
		count = 0
		s1 = s[n // 2:][::-1]
		for (i, j) in zip(range(0, n // 2), range(0, n // 2)):
			if s[i] == s1[j]:
				pass
			else:
				count += 1
			if count > k:
				break
	else:
		count = 0
		s1 = s[n // 2 + 1:][::-1]
		for (i, j) in zip(range(0, n // 2), range(0, n // 2)):
			if s[i] != s1[j]:
				count += 1
			else:
				pass
	if count <= k and n % 2 != 0:
		print('YES')
	elif k >= count and (k - count) % 2 == 0:
		print('YES')
	else:
		print('NO')