致命的な勘違いにより解けず。形式化のしすぎ。

各文字の出現回数$f_c$を考えた後、これに関する(正しい答えは導かない)整数計画問題になぜか帰着させてしまい、それを解こうとし続けてしまった。

solution

$O(N)$で頻度を数えて$O(1)$。

最終的にいくつの回文に分割することになるか考える。 $S$中に偶数回出現する文字に関して、これは回文の数を増やすことはない。 $S$中に奇数回出現する文字に関して、これはその文字を中心とした回文をひとつ要求する。 $S$中に奇数回出現する文字の種類数を$K$として、$\max \{ 1, K \}$個の回文になる。

$K = 0$は自明である。$K \ge 1$とする。 回文の個数は$K$個で、それぞれ中心に$f_c = 1 \pmod 2$なる文字$c$がある。 これらを残りの$P = \frac{N - K}{2}$組の文字らで挟んでいく。 よって$ans = 1 + 2 \cdot \lfloor \frac{P}{K} \rfloor$。

implementation

#include <iostream>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    string s; cin >> s;
    array<int,26> freq = {};
    for (char c : s) freq[c - 'a'] += 1;
    int k = 0;
    repeat (i,26) if (freq[i]) {
        if (freq[i] % 2 == 1) {
            k += 1;
        }
    }
    int n = s.length();
    int ans = k == 0
        ? n
        : 1 + (n - k) / 2 / k * 2;
    cout << ans << endl;
    return 0;
}