問題定義

2つの文字列 s と t が与えられた場合、s 内の部分文字列の中で、t のすべての文字（重複を含む）を含む最小の長さを持つものを見つけます。該当する部分文字列が存在しない場合は空文字列を返します。

この問題は、スライディングウィンドウ（Sliding Window）アルゴリズムの典型例です。左右2つのポインタを用いてウィンドウの範囲を動的に管理することで、効率的に解を見つけ出します。時間計算量は $O(|s| + |t|)$ であり、全探索を行うよりも大幅に高速です。

アルゴリズムのアプローチ

1. 文字頻度の記録: 文字列 t に含まれる各文字の出現回数を配列に記録します。ASCII文字の範囲（0～127）に限られているため、ハッシュマップよりも固定長配列を使用する方がアクセス速度が高速です。
2. ウィンドウの拡張: 右ポインタを進めてウィンドウを拡張し、現在の文字をウィンドウ内のカウントに加えます。
3. 条件の判定と収縮: ウィンドウが t の要件をすべて満たしている場合、左ポインタを進めてウィンドウを収縮させます。この過程で、条件を満たしつつ最短となる部分文字列の位置と長さを記録します。

C++による実装

以下のコードは、効率性を重視し配列を使用した実装例です。変数名やロジックの流れを最適化しています。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string findMinWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    // ASCII文字（128種類）の頻度をカウントする配列
    vector<int> targetFreq(128, 0);
    vector<int> windowFreq(128, 0);

    // 文字列tに含まれるユニークな文字の数をカウント
    int uniqueRequired = 0;
    for (char c : t) {
        if (targetFreq[c] == 0) {
            uniqueRequired++;
        }
        targetFreq[c]++;
    }

    int leftPtr = 0, rightPtr = 0;
    int formed = 0; // 条件を満たしたユニーク文字の種類数
    int minWindowLen = INT_MAX;
    int bestStart = 0;

    while (rightPtr < s.size()) {
        char c = s[rightPtr];
        windowFreq[c]++;

        // 現在の文字がtに含まれ、かつ必要数を満たしたかチェック
        if (targetFreq[c] > 0 && windowFreq[c] == targetFreq[c]) {
            formed++;
        }

        // 全ての条件を満たしている間、ウィンドウを左方向へ縮小
        while (leftPtr <= rightPtr && formed == uniqueRequired) {
            // 最小ウィンドウの情報を更新
            int currentWindowLen = rightPtr - leftPtr + 1;
            if (currentWindowLen < minWindowLen) {
                minWindowLen = currentWindowLen;
                bestStart = leftPtr;
            }

            // 左端の文字をウィンドウから除外
            char d = s[leftPtr];
            // 除外する文字がtに必要な文字であり、数が減って条件を満たさなくなる場合
            if (targetFreq[d] > 0 && windowFreq[d] == targetFreq[d]) {
                formed--;
            }
            windowFreq[d]--;
            leftPtr++;
        }

        rightPtr++;
    }

    return minWindowLen == INT_MAX ? "" : s.substr(bestStart, minWindowLen);
}

// テスト用コード
int main() {
    string s1 = "ADOBECODEBANC", t1 = "ABC";
    cout << "Result 1: " << findMinWindow(s1, t1) << endl; // 出力: BANC

    string s2 = "a", t2 = "a";
    cout << "Result 2: " << findMinWindow(s2, t2) << endl; // 出力: a

    string s3 = "a", t3 = "aa";
    cout << "Result 3: \"" << findMinWindow(s3, t3) << "\"" << endl; // 出力: "" (空)

    return 0;
}

実装のポイント

配列の利用

文字はASCIIコード（0～127）に収まるため、unordered_map などのハッシュテーブルではなく、サイズ128の整数型配列 vector<int> を使用します。配列のインデックスアクセスは $O(1)$ で行われ、ハッシュ計算や衝突処理のコストがないため、非常に高速です。

変数 formed の役割

formed 変数は、「ウィンドウ内で、必要な数（targetFreq）を満たした文字の種類」を追跡します。formed が uniqueRequired（tに含まれるユニークな文字の総数）に達したときのみ、ウィンドウの縮小処理を開始します。これにより、不要なループを防ぎ効率化しています。

ウィンドウの縮収縮ロジック

内側の while ループでは、条件を満たしている限り左ポインタ leftPtr を進めます。左端から文字を除外する際、その文字が重要な文字（tに含まれる）であり、除外することで必要数を下回るようであれば formed をデクリメントします。これにより、即座に条件が満たされなくなったことを判定し、再び右ポインタを進めるフェーズへ移行します。

計算量分析

• 時間計算量: $O(|s| + |t|)$。左右のポインタはそれぞれ最大で文字列 s の長さ分だけ移動し、t の初期化は $O(|t|)$ です。
• 空間計算量: $O(1)$。使用する配列はサイズが128で固定されており、入力サイズに依存しないため定数空间とみなせます。