【C++】1文字だけの変更で文字列を回文に変換できるか判定する方法

この記事では、与えられた文字列に対して「たった1文字を変更するだけで回文（前から読んでも後ろから読んでも同じになる文字列）にできるかどうか」を判定するC++プログラムを解説します。

問題の概要

入力として1つの文字列が与えられます。私たちのタスクは、その文字列の中から高々1文字を別の文字に置き換えることで、回文に変換できるかを判定することです。

例えば「abccaa」という文字列の場合、末尾の「a」を「b」に変更すれば「abccba」となり回文になります。このように、不一致箇所が1か所以下であれば変換は可能と判断できます。

アルゴリズムの考え方

回文であるためには、文字列の先頭からi番目の文字と、末尾からi番目の文字が必ず一致していなければなりません。この性質を利用すると、次の手順で判定できます。

• 文字列の長さをnとし、前半部分（0からn/2未満）について str[i] と str[n - i - 1] を順に比較する。
• 一致しない文字ペアの個数をカウントする。
• カウントが1以下であれば、1文字の変更で回文にできるため「Yes」、2以上であれば「No」を出力する。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// 回文への変換が可能かどうかをチェックする関数
bool if_palindrome(string str){
    int n = str.length();
    // 変更が必要な文字数をカウント
    int count = 0;
    for (int i = 0; i < n/2; ++i)
       if (str[i] != str[n - i - 1])
          ++count;
    return (count <= 1);
}
int main(){
    string str = "abccaa";
    if (if_palindrome(str))
       cout << "Yes" << endl;
    else
       cout << "No" << endl;
    return 0;
}

実行結果

Yes

コードの解説

関数 if_palindrome では、まず文字列の長さ n を取得し、不一致ペアを数えるための変数 count を0で初期化しています。その後、forループで文字列の前半分だけを走査し、対応する位置の文字が異なる場合に count をインクリメントします。

最後に count が1以下であれば true を返すことで、「1文字の変更で回文にできる」ことを表しています。main 関数ではサンプル文字列「abccaa」に対してこの関数を呼び出し、結果に応じて「Yes」または「No」を出力しています。

計算量について

このアルゴリズムは文字列の前半分のみを一度走査するため、時間計算量はO(n)、必要な追加メモリはO(1)となります。非常にシンプルかつ効率的な手法であり、長い文字列に対しても高速に動作します。