K-Palindrome Check

You are given a string S and an integer K. Your task is to determine whether it is possible to remove at most K characters from S such that the resulting string is a palindrome.

A string is a palindrome if it reads the same forward and backward. A common strategy is to determine the minimum number of deletions required to transform S into a palindrome. Let n be the length of S and LPS(S) be the length of its longest palindromic subsequence. Then the minimum number of deletions required is given by:

$$ \text{min\_deletions} = n - LPS(S) $$

If min_deletions ≤ K, then it is possible to obtain a palindrome by removing at most K characters; otherwise, it is not possible.

inputFormat

The input consists of two lines:

• The first line contains the string S.
• The second line contains the integer K.

outputFormat

Output a single line containing either True or False. Output True if it is possible to transform the input string into a palindrome by removing at most K characters; otherwise, output False.

abca
1

True