Pythonである文字列内から、別の文字列の全文字を含む最小ウィンドウを検索する方法

問題の概要

2つの文字列 s1 と s2 が与えられたとき、s1 の中から「s2 のすべての文字を含む最小の部分文字列（ウィンドウ）」を見つけます。

たとえば、入力が s1 = "I am a student"、s2 = "mdn" の場合、出力は "m a studen" になります。この部分文字列には m・d・n の3文字がすべて含まれており、これより短い範囲では条件を満たせません。

解法の考え方：スライディングウィンドウ

この問題は、スライディングウィンドウ（尺取り法）と、各文字の出現回数を記録するハッシュ配列を組み合わせることで効率的に解けます。おおまかな流れは次のとおりです。

1. 事前チェック： main_str の長さが pattern の長さより短ければ、答えは存在しないため None を返します。
2. パターンの集計： ハッシュ配列 hash_pat に、pattern 内の各文字の出現回数を記録します。比較用にもう1つの配列 hash_str を用意します。
3. ポインタの初期化： 左端 start = 0、答えの開始位置 start_index = -1、最小長 min_len = 無限大、マッチ数 count = 0 とします。
4. 右端を伸ばす： インデックス j を先頭から順に進めながら、main_str[j] の出現回数を hash_str に加算します。その文字がパターンに必要で、まだ必要数に達していなければ count を +1 します。
5. 左端を縮める： count が pattern の文字数に達したら、ウィンドウ左端の文字が不要になるまで start を進めて余分な文字を取り除きます。
6. 最小値の更新： 現在のウィンドウ幅（j − start + 1）が min_len より小さければ、min_len と start_index を更新します。
7. 結果の返却： 最後まで start_index が -1 のままなら None を返し、それ以外は main_str[start_index : start_index + min_len] を返します。

Pythonでの実装例

以下のコードで実際の動作を確認できます。ここでは、英字だけでなく空白や大文字なども扱えるよう、配列サイズを ASCII 全体をカバーする 256 としています。

N = 256

def get_pattern(main_str, pattern):
    str_len = len(main_str)
    patt_len = len(pattern)
    if str_len < patt_len:
        return None
    hash_pat = [0] * N
    hash_str = [0] * N
    for i in range(0, patt_len):
        hash_pat[ord(pattern[i])] += 1
    start, start_index, min_len = 0, -1, float('inf')
    count = 0
    for j in range(0, str_len):
        hash_str[ord(main_str[j])] += 1

        if (hash_pat[ord(main_str[j])] != 0 and
                hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
            count += 1
        if count == patt_len:
            while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]
                   or hash_pat[ord(main_str[start])] == 0):
                if hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]:
                    hash_str[ord(main_str[start])] -= 1
                start += 1
            len_window = j - start + 1
            if min_len > len_window:
                min_len = len_window
                start_index = start
    if start_index == -1:
        return None
    return main_str[start_index : start_index + min_len]

main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))

入力

"I am a student", "mdn"

出力

m a studen

計算量

各文字は右端の拡張時と左端の縮小時の合わせて高々2回しか走査されないため、時間計算量は O(n) です。また、ハッシュ配列は文字種に依存しない固定サイズなので、空間計算量は O(1) となります。