Pythonで重複文字を含まない最長部分文字列を求めるアルゴリズム

文字列が与えられたとき、同じ文字が繰り返されない最長の部分文字列（連続した部分）の長さを求める問題です。例えば、文字列が「ABCABCBB」である場合、答えは 3 になります。これは、重複する文字を一切含まない部分文字列として「ABC」（長さ3）が存在するためです。

解法のアプローチ

この問題は、スライディングウィンドウ（尺取り法）とハッシュマップを組み合わせることで効率的に解くことができます。各文字が最後に出現した位置を記録しながら、ウィンドウの左端を適切に移動させるのがポイントです。

アルゴリズムの手順

• i := 0、j := 0 と初期化し、文字の出現位置を記録するためのマップ（辞書）を用意します
• ans := 0 と初期化します
• j が文字列 s の長さ未満である間、以下を繰り返します
  • s[j] がマップに存在しない、または i > map[s[j]] の場合（現在のウィンドウ内に重複がない場合）
    • ans := max(ans, j − i + 1) で最大長を更新します
    • map[s[j]] := j で出現位置を記録します
  • それ以外の場合（重複が見つかった場合）
    • i := map[s[j]] + 1 でウィンドウの左端を移動します
    • ans := max(ans, j − i + 1) で最大長を更新します
    • j を 1 減らすことで、同じ位置を再度処理できるようにします
  • j を 1 増やします
• 最終的な ans を返します

Pythonでの実装例

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

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         j+=1
      return ans

ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

入力

"ABCABCBB"

出力

3

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量は O(min(n, m)) です。ここで n は文字列の長さ、m は使用される文字セットのサイズを表します。ハッシュマップで各文字の最新の出現位置を管理することにより、文字列を一度走査するだけで答えを導き出せる点が大きな特徴です。