# Leetcode: Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters

Similar Problems:

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/longest-substring-with-at-most-k-distinct-characters
## Basic Ideas:
##
## Complexity: Time O(n*k), Space O(k)
class Solution:
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
import collections
import sys
length = len(s)
if length <= k: return length
if k == 0: return 0
d = collections.defaultdict(lambda: 0)
index, res = length, -sys.maxsize-1
for i in range(length):
ch = s[i]
if ch in d:
d[ch] += 1
else:
if len(d) == k:
index = i
break
else:
d[ch] += 1
res = max(res, self.getCount(d))

j = 0
for i in range(index, length):
d[s[i]] += 1
while len(d) == k+1:
ch = s[j]
d[ch] -= 1
j += 1
if d[ch] == 0: del d[ch]
res = max(res, self.getCount(d))
return res

def getCount(self, d):
res = 0
for ch in d: res += d[ch]
return res
```

Share It, If You Like It.