Transform to Palindrome

You are given a string s and an integer k. You can rearrange the characters of s and modify at most k characters (i.e. change them to any other character) with the goal of transforming s into a palindrome.

A string is a palindrome if it reads the same forward and backward. In order to form a palindrome, note that at most one character can have an odd frequency. Let \(\text{odd\_count}\) be the number of characters that appear an odd number of times in s. The string can be transformed into a palindrome if and only if

\(\text{odd\_count} \leq k + 1\)

Output YES if it is possible to transform the string into a palindrome under the above conditions, or NO otherwise.

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: YES if it is possible to transform s into a palindrome by rearranging its characters and changing at most k characters, or NO otherwise.

abcba
1

YES