Description
APP stands for "Another Palindrome Problem".
Given a string str with length n and an integer k, is it possible to transform str to a palindrome(回文) by removing at most k characters?
Explanation of sample io
You are given str = "fadicaf" and you can remove 3 characters at most. In this case you can remove 'd', 'i', and get "facaf", which is a palindrome. Therefore please output "Yes". Note that there may be multiple ways to transform str to a palindrome.
Maybe useless hints
Maybe useful hints
Draw the recursion tree, and then observe how many recursive function calls with same arguments are re-calculated. Is it possible to store the result of each recursive function call once it is calculated? If so, is it possible to use the results you have stored instead of re-calculate?
Input
The first line is two integers n, k, which are string length and max number of characters you can remove.
The second line is a string str.
-
1 <= n <= 1000
-
1 <= k <= 20, for the 1-5 th test case
-
1 <= k <= 1000, for the 6 th test case. Some tricks must be applied to pass this test case.
-
str is of length n, consisting of lower case characters (a-z) only
Output
Output "Yes" (without quotation mark) in a line if str can be transformed to a palindrome by removing at most k characters, otherwise output "No" (without quotation mark) in a line.