Best solution, O(n) with two pointers, Python with explanation


  • 0
    Y
    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            if k == 0 or not s:
                return 0
            
            letter_dic = collections.defaultdict(int)
            res = 0
            max_len = 0
            i, j = 0, 0
            while j < len(s):
                letter_dic[s[j]] += 1
                if len(letter_dic) > k:
                    del letter_dic[s[j]]
                    letter_dic[s[i]] -= 1
                    if letter_dic[s[i]] == 0:
                        del letter_dic[s[i]]
                    res = max(max_len, res)
                    max_len -= 1
                    i += 1
                    
                else:
                    max_len += 1
                    j += 1
            res = max(res,max_len)
                
            return res
    

    i, j are two pointers,
    we use O(k) memory letter_dic to track the current characters, when len(letter_dic) > k, we need to move the first pointer i forward, and keep the second pointer j will stay at the same place.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.