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.
Input: String="aabccbb" Output: 3(abc)
Input: String="abbbb" Output: 2(ab)
Input: String="abccde" Sortie: 3 (abc "ou cde)
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.
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