【C++】文字列を最小回数で回文に分割し、その個数を数えるプログラム

本記事では、小文字のみで構成された文字列 s を、できるだけ少ない回数で分割し、それぞれの部分文字列がすべて回文（前から読んでも後ろから読んでも同じ文字列）になるようにする問題を解説します。そして、その分割後の部分文字列の個数を求めるプログラムを C++ で実装します。

問題の概要

例えば、入力が s = "levelracecar" の場合を考えてみましょう。この文字列は「level」と「racecar」という2つの回文に分割できるため、出力は 2 となります。

このように、与えられた文字列全体を回文の集まりに分解するとき、必要な最小の分割数（＝部分文字列の個数）を計算するのが目的です。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。基本的な考え方は以下の通りです。

• n を文字列 A の長さとします。
• サイズ (n + 1) の配列 result を定義します。result[i] は「位置 i 以降の部分文字列を回文に分割するために必要な最小の分割数」を表します。
• result[n] := -1 と初期化します。これは文字列の終端に到達したことを意味します。
• i を n - 1 から 0 まで逆順にループさせます。
• 各 i について、まず result[i] := n - i - 1 と設定します（最悪の場合、1文字ずつ分割することになります）。
• 次に j を i から n - 1 まで動かしながら、部分文字列 A[i..j] が回文であるかどうかを判定します。
• 回文であれば、result[i] := min(result[i], 1 + result[j + 1]) により、より少ない分割数へ更新します。
• 最後に result[0] + 1 を返します。これが回文の個数（＝必要な分割ブロック数）です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPalindrome(string A) {
      int left = 0;
      int right = A.size() - 1;
      while (left < right) {
         if (A[left] != A[right]) {
            return 0;
         }
         left++;
         right--;
      }
      return 1;
   }
   int solve(string A) {
      int n = A.size();
      vector<int> result(n + 1);
      result[n] = -1;
      for (int i = n - 1; i >= 0; i--) {
         result[i] = n - i - 1;
         for (int j = i; j < n; j++) {
            if (isPalindrome(A.substr(i, j - i + 1))) {
               result[i] = min(result[i], 1 + result[j + 1]);
            }
         }
      }
      return result[0] + 1;
   }
};
int solve(string s) {
   return (new Solution())->solve(s);
}
int main(){
   string s = "levelracecar";
   cout << solve(s);
}

コードのポイント

• isPalindrome 関数は、双方向ポインタ（left と right）を使って、文字列が回文かどうかを O(n) で判定します。
• solve 関数では、後ろから順に DP テーブルを埋めていくことで、各位置からの最適な分割数を求めます。
• 最終的な答えは result[0] + 1 です。DP テーブルには「切り込みの数」が記録されているため、実際の部分文字列の個数を得るには 1 を加算します。

実行結果

入力

"levelracecar"

出力

2

このように、「levelracecar」は「level」と「racecar」という2つの回文に分割できるため、正しく 2 が出力されます。

計算量について

この実装の時間計算量は O(n³) です。位置 i と j の二重ループが O(n²)、さらに各回文判定に O(n) かかるためです。文字列が長くなる場合は、回文判定を事前に DP テーブルとして計算しておくことで、O(n²) まで改善できます。競技プログラミングや面接対策としても、この最適化手法は覚えておくと役立ちます。