# 340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2, T is "ece" which its length is 3.

# Solution

Approach 1: sliding window. Can either keep a map of <char, frequency> or a map of <char, last_seen_index>. The left pointer moves 1 char at a time.

# Code (Python) (not yet verified on leetcode)

Approach 1:

def longest_substring_with_k_distinct_chars(s, k):
  if k == 0:
    return 0
  counts = {} # <char, frequency_within_window>
  # can also keep last_seen = {} <char, last_seen_index>
  back = 0
  longest = 1
  for front in range(len(s)):
    if s[front] not in counts:
      counts[s[front]] = 0
    counts[s[front]] += 1 # last_seen[s[front]] = front
    while len(counts) > k:
      counts[s[back]] -= 1 
      if counts[s[back]] == 0:
        counts.pop(s[back])
      back += 1
    # while len(last_seen) > k:  --> keep shortening the window until completely unseen a letter
    #  if last_seen[s[back]] == back:
    #    last_seen.pop(s[back])
    #  back += 1
    longest = max(longest, front - back + 1)
  return longest

# Code (C++)

Approach 1:

Approach 2: