JavaScriptで文字列内の指定文字への最短距離を求める方法

問題概要

英語の小文字アルファベットのみで構成された文字列 str を第1引数に、その文字列に必ず存在する1文字 char を第2引数にとる JavaScript 関数を作成する必要があります。

この関数は、文字列 str 内の各文字について、char で指定された文字の中で最も近いものまでの距離を計算し、その結果を配列として返します。

たとえば、次のような入力が与えられた場合を考えてみましょう。

入力：

const str = 'somestring';
const char = 's';

出力：

const output = [0, 1, 2, 1, 0, 1, 2, 3, 4, 5];

出力の配列を見ると、インデックス0の「s」は自分自身が対象文字なので距離は0、インデックス1の「o」は最も近い「s」（インデックス0）までの距離が1、といったように、各位置における最短距離が格納されています。

解決アプローチ

この問題は「左右2回の走査（Two-Pass）」によって効率的に解くことができます。

1. 左から右への走査： 各位置について、左側にある直近の char までの距離を計算します。
2. 右から左への走査： 同様に、右側にある直近の char までの距離を計算し、既存の値と比較してより小さい方を採用します。

配列の初期値は Infinity（無限大）にしておき、対象文字自身の位置では距離が 0 になります。この方法なら、時間計算量 O(n)・空間計算量 O(n) で解けるのが大きなメリットです。

コード例

const str = 'somestring';
const char = 's';

const shortestDistance = (str = '', char = '') => {
  const res = new Array(str.length).fill(Infinity);
  let prev = Infinity;

  const handleIndex = (i) => {
    if (str[i] === char) {
      prev = i;
    }
    res[i] = Math.min(res[i], Math.abs(i - prev));
  };

  // 左から右へ走査
  for (let i = 0; i < str.length; i++) {
    handleIndex(i);
  }

  // 右から左へ走査
  prev = Infinity;
  for (let i = str.length - 1; i >= 0; i--) {
    handleIndex(i);
  }

  return res;
};

console.log(shortestDistance(str, char));

出力結果

[ 0, 1, 2, 1, 0, 1, 2, 3, 4, 5 ]

コードの解説

handleIndex 関数は現在のインデックス i を受け取り、str[i] が対象文字 char と一致していれば prev を更新します。そして res[i] には、「これまでの値」と「prev との絶対的な差」のうち小さい方が代入されます。

最初のループで左方向からの距離が、2回目のループで右方向からの距離が反映されるため、最終的に各位置の最短距離が求まります。Math.abs() を使うことで、左右どちらの走査でも同じ式で距離を計算できるのがポイントです。