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

問題概要

文字列 s が与えられたとき、「異なる文字が最大2種類しか含まれない最長の部分文字列」の長さを求めることを考えます。

例えば、入力が s = "xyzzy" の場合、出力は 4 になります。これは「yzzy」が y と z の2種類の文字のみを含む最長の部分文字列だからです。

解き方：スライディングウィンドウ

この問題は「スライディングウィンドウ(尺取り法)」と呼ばれる手法を使うことで効率的に解けます。各文字の出現回数を記録するマップ(Counter)を用意し、ウィンドウ内の異なる文字の種類数が2を超えないように、左端を調整しながら右端を伸ばしていきます。

具体的な手順は以下の通りです。

• start := 0(ウィンドウの左端の位置)

• c := 各文字の出現回数を保持するマップ

• ans := 0(答えとなる最長の長さ)

• end を 0 から文字列の長さまで順に動かしながら、以下を繰り返します。

  • c[s[end]] を1増やす(右端の文字をウィンドウに追加)

  • c のサイズ(異なる文字の種類数)が2を超えている間、次の処理を繰り返します。

    • c[s[start]] を1減らす

    • c[s[start]] が0になった場合は、そのキーをマップから削除する

    • start を1進める

  • ans を ans と (end - start + 1) の大きい方の値で更新する

• 最後に ans を返します。

実装例(Python)

それでは、実際のコードを見てみましょう。

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

入力

s = "xyzzy"

出力

4

計算量について

このアルゴリズムでは、end と start がそれぞれ文字列の長さ分しか移動しないため、時間計算量は O(n) です。また、マップが保持するキーの数は異なる文字の種類数に依存するため、空間計算量も十分に小さく抑えられます。文字列が長くなっても高速に動作するのが、この手法の大きな利点です。