longest substring with no more than K distinct characters

longest_substring_with_k_distinct.py

from collections import defaultdict

def longest_substring_with_k_distinct(chars, k):
  left_idx = 0
  distinct_ct = 0
  max_ln = -1
  counter = defaultdict(int)
  for right_idx, char in enumerate(chars):
    # print("max_ln={}".format(max_ln))
    # print(
    #     "before IF: left_idx={} distinct_ct={} counter={}".format(left_idx, distinct_ct, counter))
    if not counter[char]:
      distinct_ct += 1
    counter[char] += 1
    while distinct_ct > k:
      left_chr = chars[left_idx]
      if left_chr in counter:
        counter[left_chr] -= 1
      if not counter[left_chr]:
        distinct_ct -= 1
      # print(
      #   "left_idx={} left_chr={} distinct_ct={} counter={}".format(
      #     left_idx, left_chr, distinct_ct, counter))
      left_idx += 1
    max_ln = max(max_ln, right_idx - left_idx + 1)
    # print(
    #     "after IF: left_idx={} distinct_ct={} counter={}".format(left_idx, distinct_ct, counter))
  return max_ln