Deleting to a Palindrome
National Olympiad — National round
Submission name: kpal.cpp
Problem summary
Delete at most k characters, retaining the order of the remaining characters, to obtain a palindrome. Decide whether this is possible for each test.
Input
T; for each test, k and a lowercase Latin string.
Output
A single string of T binary digits: 1 means possible, 0 means impossible.
Constraints
T < 10; 0 < k < string length < 200.
Worked example
An independently prepared example for this explanation.
Input
2 1 abca 1 abcd
Output
10
Solution analysis
- Let dp[l][r] be the fewest deletions that make the interval a palindrome.
- Equal endpoints can both remain; otherwise at least one endpoint must be removed, so take one plus the smaller neighboring interval answer.
Why it works
For unequal endpoints every palindrome deletes at least one of them, and both choices are considered. Equal endpoints can be matched around an optimal inner palindrome without increasing the minimum deletions. Induction on interval length proves the recurrence.
Watch out. Characters may be removed anywhere, not only from the ends of the original string.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For unequal endpoints every palindrome deletes at least one of them, and both choices are
// considered. Equal endpoints can be matched around an optimal inner palindrome without increasing the
// minimum deletions.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int k;
string s;
cin>>k>>s;
int n=s.size();
vector<vector<int>>d(n,vector<int>(n));
for(int len=2;len<=n;len++){
for(int l=0;l+len<=n;l++){
int r=l+len-1;
d[l][r]=s[l]==s[r]?d[l+1][r-1]:1+min(d[l+1][r],d[l][r-1]);
}
}
cout<<(d[0][n-1]<=k);
}
cout<<'\n';
}