Python o(n) Solution - Sliding Window + Counter


  • 1

    Here's how it works.

    As you iterate through the string, you implement a sliding "resizable" window. This means you need a start point to the sliding window (start = 0) and end point, which would be the index of your current iteration. The size of the sliding window is the current_index + 1 - start.

    At every index of the string, you build a hash table keeping track of the count of characters you've seen so far. When the number of keys in this hash table exceeds k, you know you've seen more than k unique characters within your sliding window.

    What do you do?

    When you've seen more than k unique characters, you want to return to a state with k unique characters inside your sliding window. How? If you've prepared a sliding window, you have a start point. Working from the start point, we can increment the start point to decrease the size of our sliding window, and decrement the count of every character we left out of the sliding window. We do this until we know we have k unique characters in our sliding window.

    All throughout this, we keep track of the largest size our sliding window gets because the sliding window represents the substring containing at most k unique characters.

    class Solution(object):
        def lengthOfLongestSubstringKDistinct(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            start = 0
            longest = 0
            char_dict = {}
            
            if not s or not k:  # not necessary but faster to short circuit
                return 0
            
            for index in xrange(len(s)):
                char = s[index]
                char_dict[char] = char_dict.get(char, 0) + 1  # track count of chars
    
                # decrease the size of sliding window until you have k unique chars in sliding window
                while len(char_dict) > k: 
                    char_dict[s[start]] -= 1
                    if char_dict[s[start]] == 0:
                        del char_dict[s[start]]
                    start += 1
    
                longest = max(longest, index+1-start)
    
            return longest
    

Log in to reply
 

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