10-line Python Solution using dictionary with easy to understand explanation


  • 23
    M
    class Solution(object):
        
        """
        The general idea is to iterate over string s.
        Always put the character c and its location i in the dictionary d.
        1) If the sliding window contains less than or equal to k distinct characters, simply record the return value, and move on.
        2) Otherwise, we need to remove a character from the sliding window.
           Here's how to find the character to be removed:
           Because the values in d represents the rightmost location of each character in the sliding window, in order to find the longest substring T, we need to locate the smallest location, and remove it from the dictionary, and then record the return value.
        """
        def lengthOfLongestSubstringKDistinct(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            # Use dictionary d to keep track of (character, location) pair,
            # where location is the rightmost location that the character appears at
            d = {}
            low, ret = 0, 0
            for i, c in enumerate(s):
                d[c] = i
                if len(d) > k:
                    low = min(d.values())
                    del d[s[low]]
                    low += 1
                ret = max(i - low + 1, ret)
            return ret

  • 0
    X

    Since the min function is used, I think the complexity is O(n*k), isn't it?


  • 0

    @xiyayan Yes, it is.


  • 4

    Share my Two pointer algorithm

    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
            d = collections.defaultdict(int)
            i, res = 0, 0
            for j in range(len(s)):
                d[s[j]] += 1
                # while have more than k, we keep removing from i
                while len(d)>k:
                    d[s[i]] -= 1
                    if d[s[i]] == 0:
                        del d[s[i]]
                    i += 1
                res = max(res, j-i+1)
            return res
    

  • 1
    A

    The while is unnecessary in your algorithm. Since we are only moving by one each time, you can change it to an if.

    @zqiu01 said in 10-line Python Solution using dictionary with easy to understand explanation:

    d = collections.defaultdict(int)
    i, res = 0, 0
    for j in range(len(s)):
    d[s[j]] += 1
    # while have more than k, we keep removing from i
    while len(d)>k:
    d[s[i]] -= 1
    if d[s[i]] == 0:
    del d[s[i]]
    i += 1
    res = max(res, j-i+1)
    return res


  • 0
    Z

    @myliu amazing solution!!! use dict.values() save one pointer. amazing


  • 1
    P

    @xiyayan @lucascho: I think the time complexity is O(n).
    The dictionary will have at most 256 characters (or whatever the alphabet size used for constructing the string is - 256 for an ascii string). Since there are a fixed number of characters therefore there are a fixed number of key-value pairs in the dictionary. And finding min with fixed number of characters will be 256 ops in the worst case which is as good as O(1). So, overall time complexity of this solution should be O(n) just due to the outermost loop.


  • 0
    X

    @pramttl
    What do you think the largest "k" could be...


Log in to reply
 

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