[PYTHON] Algorithm Gymnastics 19 No-repeat Substring

No-repeat Substring Specify a string to find the length of the longest substring with no repeating characters.

Example

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

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

Input: String="abccde" Output: 3 (abc "or cde)

Description

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.

Implementation

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