Palindrome Formation by Character Removal

You are given a string s and an integer k. Your task is to determine whether it is possible to remove exactly k characters from s so that the resulting string is a palindrome. A palindrome is a string that reads the same forwards and backwards.

The solution uses the concept of the longest palindromic subsequence (LPS). The minimum number of removals required to transform s into a palindrome is given by \( |s| - LPS(s) \), where \(|s|\) is the length of the string. If the required removals are less than or equal to k, then it is possible to obtain a palindrome by removing exactly k characters (by possibly removing additional characters in symmetric ways). Otherwise, it is impossible.

For example, consider s = "abacaba" with k = 1. Although s is already a palindrome, you can remove one character (for instance, the middle character) and still have a palindrome. Conversely, if s = "abcdef" and k = 3, the minimal removals required are greater than 3, which makes it impossible.

inputFormat

The input is read from standard input (stdin) and consists of two items:

1. A string s on the first line.
2. An integer k on the second line.

Constraints:

• s will contain only lowercase or uppercase English letters.
• k is a non-negative integer.

outputFormat

Output a single line to standard output (stdout) with either Yes if it is possible to remove exactly k characters to form a palindrome, or No otherwise.

abacaba
1

Yes