文字'a'を1文字挿入して文字列を回文でなくすC++プログラム

小文字の英字のみで構成された文字列 S が与えられます。ここで、S にちょうど 1 つだけ文字「a」を挿入することを考えます。挿入後の文字列が回文（前から読んでも後ろから読んでも同じ並びになる文字列）ではなくなるようにできた場合は、その結果の文字列を返します。どこに挿入しても回文になってしまう場合は「Impossible」を返します。

例えば、入力が S = "bpapb" の場合、末尾に「a」を追加した "bpapba" は回文ではないため、これが出力となります。

解法の考え方

この問題は、非常にシンプルなアプローチで解くことができます。「a」を末尾に追加した文字列と先頭に追加した文字列のそれぞれについて回文判定を行い、回文にならない方を採用するだけです。

アルゴリズムの手順

S + "a"（末尾に a を追加）が回文でない場合：
    return S + "a"
"a" + S（先頭に a を追加）が回文でない場合：
    return "a" + S
いずれにも該当しない場合：
    return "Impossible"

補足として、両方のパターンが回文になってしまうのは、S がすべて「a」で構成されている場合のみです。このときは「a」をどの位置に挿入しても結果が回文のまま変わらないため、答えは存在しないことになります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 回文かどうかを判定する補助関数
bool p(const string& s) {
    for (int i = 0; i < s.size() / 2; i++)
        if (s[i] != s[s.size() - 1 - i])
            return false;
    return true;
}

string solve(string S) {
    // 末尾に 'a' を追加して試す
    if (!p(S + 'a'))
        return S + 'a';
    // 先頭に 'a' を追加して試す
    else if (!p('a' + S))
        return 'a' + S;
    // どうしても回文になってしまう場合
    else
        return "Impossible";
}

int main() {
    string S = "bpapb";
    cout << solve(S) << endl;
}

コードのポイント

関数 p() は、受け取った文字列が回文かどうかを判定する補助関数です。文字列の先頭と末尾から中央に向かって文字を比較していき、一致しないペアが見つかった時点で false を返します。計算量は文字列長に対して線形時間 O(N) と効率的です。

関数 solve() では、まず S + 'a'（末尾に追加したパターン）の回文判定を行い、回文でなければその文字列を返します。次に 'a' + S（先頭に追加したパターン）を判定し、こちらも回文でなければ返します。両方とも回文になってしまった場合のみ "Impossible" を返します。

実行結果

入力

"bpapb"

出力

bpapba

入力 "bpapb" に対しては、末尾に「a」を追加した "bpapba" が出力されます。この文字列は前から読んでも後ろから読んでも並びが異なる、つまり回文ではないため、条件を正しく満たしています。