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
                if len(d) == k:
                    index = i
                    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.

Leave a Reply

Your email address will not be published.