Pythonで繰り返し文字を含まない長さKの部分文字列の個数を求める方法

問題の概要

文字列 S と整数 K が与えられたとき、「同じ文字が一度も繰り返されない」長さ K の部分文字列がいくつ存在するかを求める問題です。

例えば、S = "heyfriendshowareyou"、K = 5 の場合、答えは 15 になります。条件を満たす部分文字列は次の15個です。

[heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou]

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

すべての開始位置に対して毎回部分文字列を調べると非効率ですが、スライディングウィンドウ（尺取り法）を使えば O(N) で解けます。各文字の出現回数を記録するハッシュマップを用意し、ウィンドウを右端で拡張・左端で縮小しながら、常に「重複のない区間」を維持するのがポイントです。

アルゴリズムの手順

1. 空のマップ m を作成し、left := 0、right := -1、ans := 0 で初期化します。
2. right が「文字列の長さ - 1」未満である間、以下を繰り返します。
   • right - left + 1 == K のとき：ans を 1 増やし、m[S[left]] を 1 減らして left を 1 増やし、次の反復へ進みます。
   • S[right+1] が m に存在しないとき：m[S[right+1]] := 1 と設定し、right を 1 増やします。
   • m[S[right+1]] が 0 のとき：m[S[right+1]] を 1 増やし、right を 1 増やします。
   • それ以外（重複が発生しているとき）：m[S[left]] を 1 減らし、left を 1 増やしてウィンドウを縮めます。
3. ループ終了後も right - left + 1 == K であれば、ans を 1 増やします。
4. ans を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution(object):
   def numKLenSubstrNoRepeats(self, S, K):
      m = {}
      left = 0
      right = -1
      ans = 0
      while right < len(S) - 1:
         if right - left + 1 == K:
            ans += 1
            m[S[left]] -= 1
            left += 1
            continue
         if S[right+1] not in m:
            m[S[right+1]] = 1
            right += 1
         elif not m[S[right+1]]:
            m[S[right+1]] += 1
            right += 1
         else:
            m[S[left]] -= 1
            left += 1
      if right - left + 1 == K:
         ans += 1
      return ans

ob1 = Solution()
print(ob1.numKLenSubstrNoRepeats("heyfriendshowareyou", 5))

入力

"heyfriendshowareyou"
5

出力

15

コードのポイント

• マップ m は、現在のウィンドウ内に含まれる各文字の出現回数を管理します。
• 新しい文字を追加しようとした際に、その文字のカウントがすでに 1 以上であれば、重複が解消されるまで左端を動かします。
• ウィンドウ幅がちょうど K になったタイミングで答えをカウントします。
• 全体の時間計算量は O(N)、空間計算量は文字種の数に依存して O(min(N, アルファベットサイズ)) 程度です。