Pythonで指定した文字をすべて含む最小部分文字列の長さを求めるプログラム

2つの文字列 s と t が与えられたとき、s の中から t のすべての文字を含む最小の部分文字列（substring）の長さを求めます。該当する部分文字列が存在しない場合は -1 を返します。

たとえば、s = "thegrumpywizardmakes"、t = "wake" とすると、出力は 10 になります。「w」「a」「k」「e」の4文字をすべて含む最短の部分文字列は "wizardmake"（長さ10）であるためです。

解き方のアプローチ：スライディングウィンドウ法

この問題は、左右2つのポインタでウィンドウを伸縮させながら文字列を走査する「スライディングウィンドウ法（尺取り法）」を使うと、線形時間 O(n) で効率よく解けます。

具体的な手順は次のとおりです。

• counter := 文字列 b に含まれる各文字の出現回数を記録した辞書を作成する
• start := 0（ウィンドウの左端）
• min_subs := inf（最小部分文字列の長さ。初期値は無限大）
• rem := b に含まれる異なる文字の種類数
• end を 0 から a の長さ - 1 まで動かしながら、以下を繰り返す
  • current := a[end]
  • current が counter に存在する場合は、counter[current] を 1 減らし、0 になったら rem を 1 減らす
  • rem が 0 の間（必要な文字がすべて揃っている間）、以下を繰り返してウィンドウを左側から縮める
    • prev_char := a[start]
    • prev_char が counter に存在する場合は、counter[prev_char] を 1 増やし、正の値になったら rem を 1 増やす
    • min_subs := min_subs と (end - start + 1) のうち小さい方で更新する
    • start := start + 1
• 最後に、min_subs が無限大でなければ min_subs を返し、それ以外の場合は -1 を返す

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

class Solution:
    def solve(self, a, b):
        counter = {}
        for char in b:
            counter[char] = counter.get(char, 0) + 1
        start = 0
        min_subs = float("inf")
        rem = len(counter)
        for end in range(len(a)):
            current = a[end]
            if current in counter:
                counter[current] -= 1
                if counter[current] == 0:
                    rem -= 1
            while rem == 0:
                prev_char = a[start]
                if prev_char in counter:
                    counter[prev_char] += 1
                    if counter[prev_char] > 0:
                        rem += 1
                min_subs = min(min_subs, end - start + 1)
                start += 1
        return min_subs if min_subs != float("inf") else -1

ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))

入力

"thegrumpywizardmakes", "wake"

出力

10

計算量

時間計算量は O(n)（n は文字列 a の長さ）、空間計算量は O(k)（k は文字列 b に含まれる異なる文字の種類数）です。各文字は最大でも2回（右端の拡張時と左端の縮小時）しか処理されないため、非常に効率的なアルゴリズムとなっています。