【JavaScript】文字列から最大1文字削除して回文を作れるかどうかを判定する方法

はじめに

JavaScriptでは、文字列を第1引数（唯一の引数）として受け取る関数を書くことが求められる場面があります。

この関数の役割は、文字列から最大1文字だけ削除することで、その文字列を回文（前から読んでも後ろから読んでも同じ文字列）にできるかどうかを判定することです。回文にできる場合は true を、できない場合は false を返します。

具体例

たとえば、入力文字列が次のようになっているとします。

const str = 'kjlk';

この場合、期待される出力は次のとおりです。

const output = true;

なぜなら、文字列から「l」を1文字削除すると「kjk」が残り、これは回文だからです。

実装の考え方：双方向ポインタ（Two Pointer）

この問題は、両端から中央に向かって文字を比較していく「双方向ポインタ」のテクニックを使うと効率的に解けます。

1. 左端（left）と右端（right）のポインタを用意します。
2. 両ポインタが交わるまで、対応する2つの文字を比較します。
3. 文字が一致しない箇所を見つけたら、「右側の1文字を削除した場合」と「左側の1文字を削除した場合」のどちらかで回文になるかを確認します。
4. どちらでも回文になれば true、それ以外は false を返します。

コード例

実際のコードは次のようになります。

const str = 'kjlk';

// 指定範囲が回文かどうかを判定するヘルパー関数
const isPalindrome = (str = '', start, end) => {
    while (start < end) {
        if (str[start] !== str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
};

// 最大1文字の削除で回文にできるかを判定する本体関数
const canMakePalindrome = (str = '') => {
    let left = 0, right = str.length - 1;
    while (left < right - 1) {
        if (str[left] !== str[right]) {
            // 右側の文字を削除してみる
            if (isPalindrome(str, left, right - 1)) {
                return true;
            }
            // 左側の文字を削除してみる
            if (isPalindrome(str, left + 1, right)) {
                return true;
            }
            // どちらでも回文にならない
            return false;
        } else {
            left++;
            right--;
        }
    }
    return true;
};

console.log(canMakePalindrome(str));

出力結果

コンソールには次のように出力されます。

true

処理の流れを詳しく見る

例として挙げた 'kjlk' の場合、処理は以下のように進みます。

1. 最初の比較：str[0]（k）と str[3]（k）→ 一致するのでポインタを内側へ移動。
2. 次の比較：str[1]（j）と str[2]（l）→ 不一致！
3. ここで分岐します。
   • str[2]（l）を削除して「kjk」→ 回文なので true を返す。

このアルゴリズムの計算量は O(n) で、文字列を1周するだけなので非常に高速です。全パターンを総当たりする方法（O(n²) 以上）と比べて、長い文字列でも実用的に動作するのが大きなメリットです。

まとめ

文字列がすでに回文である場合も、0文字の削除（＝削除なし）で条件を満たすため true が返されます。不一致箇所が見つかった時点で左右それぞれの削除パターンだけを検証すればよいため、シンプルかつ効率的に判定できるのがこの手法のポイントです。