[PYTHON] Algorithmus Gymnastik 19 No-Repeat-Teilzeichenfolge

No-repeat Substring Geben Sie eine Zeichenfolge an, um die Länge des längsten Teilstrings ohne sich wiederholende Zeichen zu ermitteln.

Beispiel

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

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

Input: String="abccde" Ausgabe: 3 (abc "oder cde)

Erläuterung

Bei diesem Problem handelt es sich um ein Schiebefenstermuster, mit dem Sie eine dynamische Schiebefensterstrategie verwenden können. Sie können HashMap (dict) verwenden, um den letzten Index jedes verarbeiteten Zeichens zu speichern. Verkleinern Sie jedes Mal, wenn Sie ein sich wiederholendes Zeichen erhalten, das Schiebefenster, um sicherzustellen, dass das Schiebefenster immer unterschiedliche Zeichen enthält.

Implementierung

python

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