Minimum Window Substring

スライディングウィンドウ法による効率的な部分文字列検索アルゴリズム

アルゴリズム概要

Minimum Window Substring問題は、文字列sの中から文字列tのすべての文字を含む最小の部分文字列を見つける問題です。 この問題はスライディングウィンドウ法と2ポインタ法を組み合わせることで、O(m+n)の時間計算量で効率的に解くことができます。

核心アイデア

  • ウィンドウを拡張して条件を満たす
  • 条件を満たしたらウィンドウを収縮して最小化
  • 文字頻度をハッシュマップで効率的に管理

ステップバイステップ解説

1

初期化

文字列tの文字頻度をハッシュマップneedに記録し、現在のウィンドウの状態を追跡する変数を初期化します。

2

ウィンドウ拡張

右ポインタを移動して文字を追加し、haveハッシュマップを更新。追加した文字が条件を満たすかチェックします。

3

条件判定

formed == requiredの時、現在のウィンドウは有効。この状態でウィンドウの最小化を試みます。

4

ウィンドウ収縮

左ポインタを移動してウィンドウを縮小。有効な間は最小ウィンドウを更新し、無効になったら拡張に戻ります。

実装コード

Python実装 - 業務用バージョン 
from typing import Dict, Optional
from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        最小ウィンドウ部分文字列を返す
        Args:
            s (str): 探索対象文字列
            t (str): 必要文字列
        Returns:
            str: 条件を満たす最小部分文字列。存在しない場合は空文字。
        """
        # 入力検証
        if not isinstance(s, str) or not isinstance(t, str):
            raise TypeError("Both s and t must be strings")
        if not t:
            raise ValueError("String t must not be empty")
        if len(s) < len(t):
            return ""

        # t の文字頻度を記録
        need: Dict[str, int] = defaultdict(int)
        for ch in t:
            need[ch] += 1

        # ウィンドウ状態の管理
        have: Dict[str, int] = defaultdict(int)
        required = len(need)  # 必要な文字種類数
        formed = 0            # 現在満たしている文字種類数
        res: Optional[tuple[int, int]] = None  # 結果のインデックス
        l = 0                 # 左ポインタ

        # スライディングウィンドウ
        for r, ch in enumerate(s):
            # ウィンドウを右に拡張
            have[ch] += 1
            if ch in need and have[ch] == need[ch]:
                formed += 1

            # 有効なウィンドウの間、左端を縮める
            while formed == required:
                # 最小ウィンドウを更新
                if res is None or (r - l) < (res[1] - res[0]):
                    res = (l, r)

                # 左端の文字を除去
                left_ch = s[l]
                have[left_ch] -= 1
                if left_ch in need and have[left_ch] < need[left_ch]:
                    formed -= 1
                l += 1

        return "" if res is None else s[res[0]:res[1]+1]
Python実装 - 競技プログラミング用最適化版 
def minWindow_optimized(s: str, t: str) -> str:
    """競技プログラミング向け高速版"""
    need = defaultdict(int)
    for ch in t:
        need[ch] += 1

    have = defaultdict(int)
    required, formed = len(need), 0
    res, l = None, 0

    for r, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        while formed == required:
            if res is None or (r - l) < (res[1] - res[0]):
                res = (l, r)
            left_ch = s[l]
            have[left_ch] -= 1
            if left_ch in need and have[left_ch] < need[left_ch]:
                formed -= 1
            l += 1

    return "" if res is None else s[res[0]:res[1]+1]

視覚的デモンストレーション

例: s = "ADOBECODEBANC", t = "ABC"

状態: 待機中

計算量解析

時間計算量

O(m + n)

各文字は最大2回処理される（右ポインタと左ポインタで各1回）

空間計算量

O(1)

英字のみの制約により、ハッシュマップのサイズは最大52で定数

Python固有の最適化ポイント

実装のポイント

効率化テクニック

文字種類数での判定: 全文字頻度を毎回比較するのではなく、formed変数で満たした文字種類数を追跡することで高速化

エラーハンドリング