JavaScriptで最小ウィンドウ部分文字列を求める方法

JavaScriptで、2つの文字列(str1とstr2)を受け取る関数を作成します。str1の長さは必ずstr2より長いことが保証されています。求めるのは、str2に含まれるすべての文字を含む、str1内の最短の連続部分文字列(最小ウィンドウ)です。

問題の例

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

const str1 = 'abcdefgh';
const str2 = 'gedcf';

このとき、出力は次のようになります。

const output = 'cdefg';

「cdefg」は、str2のすべての文字(g、e、d、c、f)を含む、str1内で最も短い連続部分文字列だからです。

解決アプローチ

最もシンプルな方法は総当たり(ブルートフォース)です。str1から生成できるすべての部分文字列を順に取り出し、それぞれがstr2の全文字を含んでいるかをチェックします。条件を満たす文字列の中で最も短いものを答えとします。

コード例

以下がその実装です。

const str1 = 'abcdefgh';
const str2 = 'gedcf';

// testStringがstr2のすべての文字を含むかを判定する補助関数
const subIncludesAll = (str, str2) => {
  for (let i = 0; i < str.length; i++) {
    if (str2.indexOf(str[i]) !== -1) {
      str2 = str2.replace(str[i], '');
    }
  }
  return (str2.length === 0);
};

const minWindow = (str1 = '', str2 = '') => {
  let shortestString = null;
  for (let i = 0; i < str1.length; i++) {
    for (let j = i; j < str1.length; j++) {
      let testString = str1.substr(i, j - i + 1);
      if (subIncludesAll(testString, str2)) {
        if (shortestString === null || testString.length < shortestString.length) {
          shortestString = testString;
        }
      }
    }
  }
  return shortestString;
};

console.log(minWindow(str1, str2));

出力

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

cdefg

コードの解説

subIncludesAll関数は、第1引数の文字列が、第2引数の文字列に含まれるすべての文字を網羅しているかを判定します。対象の文字が見つかるたびにstr2からその文字を1つ取り除き、最終的にstr2が空文字列になれば「すべて含まれている」と判断します。

minWindow関数は、2重ループによってstr1のすべての部分文字列を生成します。各部分文字列に対してsubIncludesAllで判定を行い、条件を満たすものの中で最も短い文字列をshortestStringとして記録していきます。

計算量と改善のヒント

この総当たりアプローチの計算量は文字列長をnとするとO(n³)程度となり、入力が長くなると非効率になります。実務やコーディング面接では、スライディングウィンドウ(尺取り法)を用いたO(n)の解法が推奨されます。これは左右のポインタを動かしながらウィンドウを拡大・縮小し、ハッシュマップで各文字の出現回数を管理することで、必要な文字がすべて揃った瞬間にウィンドウを縮めて最短を更新していく手法です。