Rearrange to Palindrome with Limited Replacements

You are given a string s and an integer k. Your task is to determine if it is possible to rearrange the characters in s to form a palindrome by performing at most k character replacements. In a palindrome, all characters have even frequency except at most one character which can appear an odd number of times.

Formally, let \( o \) be the number of characters in s that appear an odd number of times. A palindrome can be formed if and only if \( o \leq 1 \) without requiring any replacement. Otherwise, you need to make at least \( o - 1 \) replacements. Your answer should be True if \( k \geq o - 1 \) (or if the string already can form a palindrome), and False otherwise.

Examples:

• Input: s = "aabbcc", k = 0; Output: True
• Input: s = "aabbcc", k = 2; Output: True
• Input: s = "aabbccc", k = 1; Output: True
• Input: s = "aabbccd", k = 1; Output: True
• Input: s = "abc", k = 1; Output: False

inputFormat

The input is given from stdin and consists of two lines:

1. The first line contains the string s consisting of lowercase letters.
2. The second line contains an integer k, representing the maximum number of allowed replacements.

outputFormat

Output a single line to stdout with either True or False indicating whether it is possible to rearrange the string into a palindrome with at most k replacements.

## sample

aabbcc
0

True

</p>