C++で文字列からk個の回文を作成できるか判定する方法

文字列 s と整数 k が与えられたとします。ここでの課題は、s に含まれるすべての文字を使って、k 個の空でない回文（パリンドローム）文字列を構築できるかどうかを判定することです。

例えば、入力が "true"、k = 4 の場合を考えてみましょう。この場合、各文字をそれぞれ別の文字列に割り当てるしか方法がないため、出力は True になります。

解決のアプローチ

この問題を解く鍵となるのは、回文の性質です。回文では、奇数回出現する文字は最大で 1 種類しか許されません。したがって、k 個の回文を構築できるかどうかは、「奇数回出現する文字の種類数」が k 以下であるかどうかで決まります。

以下の手順で解くことができます。

• n := 文字列 s の長さ
• n < k の場合 → false を返す（文字数が足りず、k 個の空でない文字列を作れないため）
• n == k の場合 → true を返す（各文字を 1 つずつ別々の文字列にすればよいため）
• マップ（連想配列）を 1 つ定義する
• s の各文字 c について、m[c] を 1 ずつ増やす（出現回数をカウント）
• odd := 0 とする
• マップ m の各キー・値ペア it について、odd に「値 AND 1」（出現回数が奇数なら 1）を加算する
• odd <= k なら true、それ以外は false を返す

実装例

理解を深めるために、以下の C++ 実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canConstruct(string s, int k) {
      int n = s.size();
      if (n < k)
         return false;
      if (n == k)
         return true;
      map<char, int> m;
      for (char c : s)
         m[c]++;
      int odd = 0;
      for (auto& it : m) {
         odd += (it.second & 1);
      }
      return odd <= k;
   }
};
main(){
   Solution ob;
   cout << (ob.canConstruct("true",4));
}

入力

"true"

出力

1

このアルゴリズムの計算量は、文字列の長さを n とすると O(n) であり、非常に効率的です。文字数の事前チェックと奇数回出現文字のカウントというシンプルな考え方だけで、問題を解決できる点がポイントです。