Would this solution also be O(n)?
def longest_substring_with_k_distinct(str, k):
window_start, max_length = 0, 0
if k <= 0:
return 0
for window_end in range(0, len(str)):
if len(set(str[window_start: window_end + 1])) <= k:
max_length = max(max_length, window_end - window_start + 1)
else:
while len(set(str[window_start: window_end + 1])) > k:
window_start += 1
return max_length
It passes all the tests but I’m not sure about the efficiency of creating a new set and using the length to determine the number of distinct characters.