PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: S.Manuj Nanthan
Tester: Tejas Pandey
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
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?
QUICK EXPLANATION:
- Let Z be the minimum number of operations required to convert the string into a palindrome.
- The answer is
NO
if Z>K. - If Z \leq K and N is odd, the answer is
YES
. - If Z \leq K and N is even, the answer is
YES
if K-Z is even. Otherwise, the answer isNO
.
EXPLANATION:
What is a palindrome?
A binary string S of length N is said to be a palindrome if S_i = S_{N-i+1} for 1 \leq i \leq N.
Minimum operations required
Let us find the minimum number of operations required to convert S into a palindrome.
While traversing the string, we check if S_i \neq S_{N-i+1}. In this case, we can flip S_i using one operation and increment the count of operations.
The final count of operations is the minimum number of operations required.
Note that you do not need to traverse the whole string. You can find the count by traversing the first half of the string.
If the minimum number of operations required is greater than K, we can never make the string palindrome and the answer is NO
.
Handling extra operations
We know that we need to apply exactly K operations on the string.
Suppose that we convert the string into a palindrome using minimum operations and we still have X operations left (X>0). There are two possible cases:
-
String is of odd length: We apply all the X operations on the middle character of the string. Since the string is of odd length, it would remain a palindrome, no matter how many times we flip the middle character. Thus, the answer is
YES
in this case. -
String is of even length: If we flip a character, we need to flip it back so that the string remains a palindrome. This means that, to keep it a palindrome, we can only apply an even number of operations on the string. Thus, the answer is
YES
if X is even andNO
otherwise.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
need=0
for i in range(n//2):
if(s[i]!=s[n-i-1]):
need+=1
if(need > k):
print("NO")
else:
if(n%2 or (n%2==0 and ( (k-need)%2==0))):
print("YES")
else:
print("NO")
Tester's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int cnt = 0;
for(int i = 0; i < n/2; i++)
cnt += (s[i] != s[n - 1 - i]);
if(k < cnt) cout << "NO\n";
else {
if(n&1) cout << "YES\n";
else {
if((k - cnt)&1) cout << "NO\n";
else cout << "YES\n";
}
}
}
return 0;
}
Editorialist's Solution
#include <iostream>
#include <string.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
string s;
cin>>s;
int reqd = 0;
for(int i = 0; i<n/2; i++){
if(s[i]!=s[n-1-i]){
reqd++;
}
}
if(reqd>k){
cout<<"NO";
}
else if(n%2 || (n%2==0 && (k-reqd)%2==0)){
cout<<"YES";
}
else{
cout<<"NO";
}
cout<<endl;
}
return 0;
}