Pythonで最大k種類の異なる文字を含む最長部分文字列の長さを求める方法

数値 k と文字列 s が与えられたとき、最大で k 種類の異なる文字を含む最長の部分文字列（substring）の長さを求める問題について解説します。

例えば、k = 3、s = "kolkata" が入力として与えられた場合、出力は 4 になります。これは、「kolk」と「kata」という2つの部分文字列がどちらも3種類の異なる文字を含み、その長さが4であるためです。

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

この問題は「スライディングウィンドウ（sliding window）」という手法を使うことで効率的に解けます。ウィンドウの右端を1つずつ進めながら、ウィンドウ内に含まれる異なる文字の種類数をハッシュマップ（辞書）で管理し、種類数が k を超えた場合には左端を縮めて調整していくのが基本的な考え方です。

アルゴリズムの手順

• 答えを格納する ans とウィンドウ左端の left を 0 で初期化します。
• 各文字の出現回数を記録するマップ table を作成します。
• right を 0 から文字列の長さ - 1 まで順に処理します。
  • table[s[right]] のカウントを 1 増やします（キーが存在しない場合は 0 からスタート）。
  • マップのサイズ（異なる文字の種類数）が k 以下であれば、ans と現在のウィンドウ幅 (right - left + 1) の大きい方で ans を更新します。
  • それ以外の場合は、マップのサイズが k 以下になるまで左端を縮め続けます。
    • left_char = s[left] を取得します。
    • table[left_char] が 1 であれば、そのキーをマップから削除します。
    • そうでなければ、table[left_char] を 1 減らします。
    • left を 1 増やします。
• 最後に ans を返します。

実装例

以下がPythonでの実装例です。

class Solution:
   def solve(self, k, s):
      ans = 0
      left = 0
      table = {}
      for right in range(0, len(s)):
         table[s[right]] = table.get(s[right], 0) + 1
         if len(table) <= k:
            ans = max(ans, right - left + 1)
         else:
            while len(table) > k:
               left_char = s[left]
               if table[left_char] == 1:
                  table.pop(left_char)
               else:
                  table[left_char] -= 1
               left += 1
      return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))

入力

k = 3, s = "kolkata"

出力

4

計算量について

このアルゴリズムの時間計算量は O(n) です。右端 right は文字列を一度だけ走査し、左端 left も後戻りせず前進するだけなので、全体を線形時間で処理できます。空間計算量は、マップに保持される文字の種類数に依存し、最大でも O(k) 程度に抑えられます。