C++で文字から構築できる最長回文の長さを求める方法

本記事では、C++を使って「与えられた文字列の文字から構築できる最長回文の長さ」を求めるアルゴリズムを解説します。

問題の概要

小文字・大文字の英字のみで構成された文字列が与えられたとき、それらの文字を自由に並べ替えて作れる最長の回文の長さを求めます。なお、この問題では大文字と小文字は区別されるため、「Aa」のような組み合わせは回文とはみなされません。

例えば、入力が "abccccdd" の場合、出力は 7 になります。これは、"dccaccd" のような長さ7の回文を構築できるためです。

解法のアプローチ

回文の性質に着目すると、以下のように考えることができます。

• 偶数個出現する文字は、すべて左右対称に配置できるため全て使えます。
• 奇数個出現する文字は、そのうち1種類だけ中央に置くことができます（残りは偶数分のみ使用）。

この考え方をもとに、次の手順で解きます。

1. 各文字の出現回数を記録するマップ mp を定義します。
2. 文字列 s 内の各文字について、mp のカウントを1ずつ増やします。
3. 変数 ma = 0（奇数個出現した文字の種類数）、c = 0（文字の総数）、ans = 0（答え）を初期化します。
4. マップ内の各キーと値のペアを走査し、値が奇数なら ma を1増やします。また、c に出現回数を加算します。
5. ma > 0 なら、ma を1減らします（中央に置ける文字は1つのため）。
6. ans = c - ma を計算して返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> mp;
        for (auto i : s)
            mp[i]++;
        int ma = 0, c = 0, ans = 0;
        for (auto i : mp) {
            if ((i.second) % 2 == 1)
                ma++;
            c += i.second;
        }
        if (ma > 0)
            ma--;
        ans = c - ma;
        return ans;
    }
};
main(){
    Solution ob;
    cout << (ob.longestPalindrome("abccccdd"));
}

入力

"abccccdd"

出力

7

計算量

このアルゴリズムの時間計算量は O(n)（n は文字列の長さ）、空間計算量は O(1) です。マップに格納されるキーの種類数は英字52種類に限定されるためです。