Educational Codeforces Round 2 C. Make Palindrome

問題

codeforces.com

解法

回文になっているためには,

• 文字列の長さが偶数の場合, すべての文字が偶数個ずつ
• 文字列の長さが奇数の場合, 1 つの文字を除いて, すべての文字が偶数子ずつ

ある必要があります。

で, 辞書順最小にすることを考えると, ある文字のペア (c, d) (c < d を満たす)があって, どちらの文字数も奇数である場合, (c, c) と変換すると良いです。

int cnt[26];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) cnt[s[i]-'a']++;
    int l = 0, r = 25;
    while (l < r) {
        if (cnt[l]%2 == 0) {
            l++;
            continue;
        }
        if (cnt[r]%2 == 0) {
            r--;
            continue;
        }
        cnt[l++]++;
        cnt[r--]--;
    }
    string ans;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < (cnt[i])/2; j++) ans += (char)('a'+i);
    }
    for (int i = 0; i < 26; i++) if (cnt[i]%2) ans += (char)('a'+i);
    for (int i = 25; i >= 0; i--) {
        for (int j = 0; j < cnt[i]/2; j++) ans += (char)('a'+i);
    }
    cout << ans << endl;
    return 0;
}