JavaScriptで文字列から欠落している文字を見つける方法

文字列の長さが m で、その中に英アルファベットの最初の m 文字が含まれているとします。しかし何らかの理由で、そのうちの 1 文字が文字列から欠落してしまい、実際には m-1 文字しか含まれていない状態になっています。

このような文字列を引数として受け取り、欠落している 1 文字を返す関数を JavaScript で作成していきましょう。

実装のアプローチ

この問題は、アルファベットの各文字（a 〜 z に対応する文字コード 97 〜 122）を順番にチェックし、文字列に含まれていない最初の文字を見つけることで解決できます。

具体的には、以下の手順で処理を行います。

• 関数の一貫性を高めるため、受け取った文字列をすべて小文字に変換します。
• 文字コード 97（'a'）から順にループ処理を行います。
• 各文字コードを String.fromCharCode() で文字に変換し、文字列に含まれているかどうかを includes() で判定します。
• 含まれていなければ、その文字が欠落している文字なので、それを返して処理を終了します。

コード例

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

const str = "acdghfbekj";
const missingCharacter = str => {
  // 関数の一貫性を高めるため小文字に変換
  const s = str.toLowerCase();
  for(let i = 97; ; i++){
    if(s.includes(String.fromCharCode(i))){
      continue;
    };
    return String.fromCharCode(i);
  };
  return false;
};
console.log(missingCharacter(str));

出力結果

コンソールに出力される結果は以下のとおりです。

i

この例では、入力文字列 "acdghfbekj" には a から k までの 11 文字のうち 10 文字が含まれており、欠落しているのは「i」であるため、正しく「i」が出力されます。

補足

このアプローチはシンプルで直感的ですが、includes() を文字ごとに呼び出すため、最悪の場合の計算量は O(m²) になります。文字列が長くなる場合は、Set を使って文字の存在判定を O(1) にすることで、全体の計算量を O(m) に改善できます。