No-repeat Substring Specify a string to find the length of the longest substring with no repeating characters.
Input: String="aabccbb" Output: 3(abc)
Input: String="abbbb" Output: 2(ab)
Input: String="abccde" Output: 3 (abc "or cde)
This issue is a sliding window pattern, and you can use a dynamic sliding window strategy. You can use HashMap (dict) to remember the last index of each character processed. Every time you get a repeating character, shrink the sliding window to make sure that the sliding window always has different characters.
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