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

Recommended Posts

Algorithm Gymnastics 19 No-repeat Substring
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List