C++で文字列を並べ替えて回文部分文字列の数を最大化する方法

任意の長さの文字列 str が与えられたとき、入力文字列から文字を追加・削除することなく、回文となっている部分文字列の数が最大になるように文字を並べ替えるのが本記事の課題です。回文とは、先頭から読んでも末尾から読んでも同じ並び・同じ読み方になるように文字が配置された文字列のことを指します。

入出力シナリオ

まず、いくつかの入出力パターンを見てみましょう。

例 1

入力：string str = "itnin"

出力：回文部分文字列の数を最大化するための文字列の並べ替え結果は「iinnt」です。

解説：文字列型変数 str が与えられています。入力文字列の各文字を、回文となる部分文字列の数が最大になるように並べ替えます。並べ替えが不可能な場合は「NOT POSSIBLE」を返すものとします。この入力文字列の場合、出力は「iinnt」になります。

例 2

入力：string str = "abaaaabb"

出力：回文部分文字列の数を最大化するための文字列の並べ替え結果は「aaaaabbb」です。

解説：同様に文字列型変数 str が与えられています。文字をうまく並べ替えて、回文となる部分文字列の数を最大にします。この入力文字列の場合、出力は「aaaaabbb」になります。

プログラムで採用しているアプローチ

この問題は、同じ文字をすべて隣接するように並べ替える（＝文字を昇順にソートする）ことで解決できます。同じ文字が連続したブロックを形成すれば、そのブロック内のどの部分文字列も自然と回文になるため、回文部分文字列の数が最大になります。具体的な手順は以下の通りです。

• 文字列型の変数（ここでは str とします）を入力として受け取り、文字列のサイズを計算して length という名前の変数に格納します。

• データを関数 Rearr_string(str, length) に渡します。

• 関数 Rearr_string(str, length) の内部では以下の処理を行います。

  • サイズ 26 の整数型配列 arr[26] を宣言し、0 で初期化します。

  • 文字列型の一時変数 temp を宣言します。

  • i を 0 から length 未満まで for ループで回します。ループ内では arr[str[i] - 'a']++ として、各文字（a〜z）の出現回数をカウントします。

  • i を 0 から 26 未満まで for ループで回し、その内部でさらに j を 0 から arr[i] 未満まで for ループで回します。ループ内では temp = temp + (char)(97 + i) として、出現回数のぶんだけ同じ文字を temp に連結していきます。

  • temp を返します。

• 結果を出力します。

サンプルコード（C++）

#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
    int arr[26] = { 0 };
    string temp = "";
    for(int i = 0; i < length; i++){
        arr[str[i] - 'a']++;
    }
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < arr[i]; j++){
            temp = temp + (char)(97 + i);
        }
    }
    return temp;
}
int main(){
    string str = "itnin";
    int length = str.length();
    cout<<"回文部分文字列の数を最大化するための文字列の並べ替え結果："<<Rearr_string(str, length);
    return 0;
}

実行結果

上記のコードを実行すると、以下のような出力が得られます。

回文部分文字列の数を最大化するための文字列の並べ替え結果：iinnt

このように、単純に文字を昇順へ並べ替えるだけで、同じ文字同士が連続したブロックを形成し、回文となる部分文字列の数が最大化されることが分かります。