アルゴリズム 体操19 No-repeat Substring

No-repeat Substring

文字列を指定して、繰り返し文字がない最長の部分文字列の長さを見つけます。

例

Input: String="aabccbb"
Output: 3(abc)

Input: String="abbbb"
Output: 2(ab)

Input: String="abccde"
Output: 3 (abc" または cde)

説明

この問題はスライディングウィンドウパターンで、動的スライディングウィンドウ戦略を使用できます。 HashMap(dict)を使用して、処理した各文字の最後のインデックスを記憶できます。 繰り返し文字を取得するたびに、スライディングウィンドウを縮小して、スライディングウィンドウに常に異なる文字があることを確認します。

実装

from collections import defaultdict

def non_repeat_substring(str1):
  window_start = 0
  max_length = 0
  substring_frequency = defaultdict(int)

  for window_end in range(len(str1)):
    right_char = str1[window_end]
    substring_frequency[right_char] += 1
    while substring_frequency[right_char] > 1:
      left_char = str1[window_start]
      substring_frequency[left_char] -= 1
      if substring_frequency[left_char] == 0:
        del substring_frequency[left_char]
      window_start += 1
    max_length = max(max_length, window_end - window_start + 1)

  return max_length