C++で回文を壊す：辞書順最小の非回文文字列を作るアルゴリズム

問題概要

回文（前から読んでも後ろから読んでも同じになる文字列）が与えられます。この文字列に対して、ちょうど1文字を任意の小文字の英字に置き換え、回文ではなくなる文字列のうち辞書順最小のものを作ります。そして、その結果得られる最終的な文字列を求めてください。どうしても回文を壊せない場合は、空文字列を返します。
例えば、入力が "abccba" の場合、出力は aaccba となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。辞書順最小の文字列を作るには、「可能な限り前方の文字を小さくする」という性質を利用するのがポイントです。

アルゴリズムの手順

• changed := false と初期化する
• 文字列の長さが1の場合は空文字列を返す（1文字の置換では必ず再び回文になるため）
• i := 0、j := 文字列の長さ - 1 とする
• i < j の間、次を繰り返す：
  • s[i] が 'a' でなければ、s[i] を 'a' に書き換えて s を返す
  • i を1増やし、j を1減らす
• ループを抜けた場合（すべての文字が 'a' の場合）、末尾の文字を 'b' に変更する
• s を返す

なぜこの方法が有効なのか

• 英小文字には 'a' より小さい文字が存在しないため、左側から見て最初に見つかった 'a' 以外の文字を 'a' に置き換えるのが最適です。
• すべての文字が 'a' の場合（例："aaa"）、辞書順最小を保ちつつ回文を壊すには、末尾の文字を 'b' にするしかありません。
• 長さ1の文字列は、どの1文字を置き換えても回文のままなので、条件を満たす答えは存在せず、空文字列を返します。

C++での実装例

以下の実装を見ると、理解がさらに深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string breakPalindrome(string s) {
        bool changed = false;
        if(s.size() == 1)return "";
        int i = 0, j = s.size() - 1;
        bool leftA = true;
        bool rightA = true;
        while(i < j){
            if(s[i] != 'a'){
                s[i] = 'a';
                return s;
            }
            i++;
            j--;
        }
        s[s.size() - 1] = 'b';
        return s;
    }
};
main(){
    Solution ob;
    cout << (ob.breakPalindrome("abccba"));
}

入力

"abccba"

出力

aaccba

計算量

• 時間計算量：O(n) ― 文字列を高々1回走査するだけです。
• 空間計算量：O(1) ― 入力文字列を直接書き換えるため、追加のメモリはほぼ不要です。