PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You have a string S of A-s and B-s.
In one operation, you can choose two adjacent equal characters and delete one of them.
Can you obtain a string of length exactly K?
EXPLANATION:
Let’s split S into maximal blocks of equal characters, for example BBBAAAAAAB splits into BBB, AAAAAA, B.
Let B denote the number of blocks.
Observe that two adjacent equal characters always belong to the same block.
So, an operation always deletes exactly one character from some block that has length at least 2, reducing its length by 1 (but never letting its length become 0.)
Since the count of blocks doesn’t change, the final string also must have exactly B blocks of positive size - which means it must have at least B characters.
So, if K \lt B, no solution exists and the answer is No.
On the other hand, every length between B and N is reachable: each operation reduces the length by exactly 1, and we can keep operating till every block has length 1, at which point the length is B.
So, if K \ge B, the answer is YES.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
blocks = 1
for i in range(1, n):
blocks += s[i] != s[i-1]
print('Yes' if blocks <= k <= n else 'No')