Gymnastique d'algorithme 19 Sous-chaîne sans répétition

No-repeat Substring Spécifiez une chaîne pour trouver la longueur de la plus longue sous-chaîne sans caractère répétitif.

Exemple

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

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

Input: String="abccde" Sortie: 3 (abc "ou cde)

La description

Ce problème est un modèle de fenêtre coulissante qui vous permet d'utiliser une stratégie de fenêtre coulissante dynamique. Vous pouvez utiliser HashMap (dict) pour mémoriser le dernier index de chaque caractère traité. Chaque fois que vous obtenez un caractère répétitif, réduisez la fenêtre coulissante pour vous assurer que la fenêtre coulissante a toujours des caractères différents.

la mise en oeuvre

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

Recommended Posts

Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée