# 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: