educative.io

Simpler solution compared with official one

Courses
,
#1

the key difference is that it keeps track of the latest position of the char not the frequency.

def longest_substring_with_k_distinct(str1, k):
  max_len = window_start = 0
  existed_c = {}
  for window_end, value in enumerate(str1):
    existed_c[value] = window_end

    while len(existed_c) > k:
      if existed_c[str1[window_start]] == window_start:
        del existed_c[str1[window_start]]
      window_start += 1
    
    max_len = max(max_len, window_end-window_start+1)
  
  return max_len
#2

Hi @chance,

Your solution to the problem is correct, as you know there are multiple solutions to the same problem, we just chose the one that can be most intuitive for the user to understand, moreover, the time complexity and space complexity of the two solutions remains the same.

1 Like