AT_code_festival_2017_qualc_d Yet Another Palindrome Partitioning

给定一个字符串$\texttt{s}$，把$\texttt{s}$分成$N$个子串，要求每个子串中的字母经过一定的移动，会变成一个回文串（如`aab`经过一定的移动，变成了`aba`，`aba`是一个回文串），**且$N$最少**。

一个字符串$\texttt{s}$（$1 \le \texttt{|s|} \le 2 \times 10^5$）

一个正整数$N$，表示最少的子串个数。

### 制約 - $ 1\ \leq\ |s|\ \leq\ 2\ \times\ 10^5 $ - $ s $ は英小文字のみからなる。 ### Sample Explanation 1 `aabxyyzz` = `aab` + `xyyzz` と分割すればよいです。 このとき、`aab` の文字を並べ替えて回文 `aba` が得られ、`xyyzz` の文字を並べ替えて回文 `zyxyz` が得られます。 ### Sample Explanation 2 `byebye` の文字を並べ替えて回文 `byeeyb` が得られます。 ### Sample Explanation 4 `abcabcxabcx` = `a` + `b` + `cabcxabcx` と分割すればよいです。