340.Longest Substring with At Most K Distinct Characters

Tags: [pointer], [window], [sliding_window], [shrink_window], [map]

Com: {g}

Link: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/\#/description

Given a string, find the length of the longest substring T that contains at mostkdistinct characters.

For example, Given s =“eceba”and k = 2,

T is "ece" which its length is 3.

Solution: Sliding Window, Map

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s or not k:
            return 0

        char_counts = {}
        max_len = 0
        start = 0
        end = 0

        while end < len(s):
            curr = s[end]
            if curr not in char_counts:
                char_counts[curr] = 1
            else:
                char_counts[curr] += 1

            if len(char_counts) > k:
                curr_len = end - start
                max_len = max(max_len, curr_len)

                # shrink the window by moving the start to right.
                while len(char_counts) > k:
                    char_counts[s[start]] -= 1
                    if char_counts[s[start]] == 0:
                        del char_counts[s[start]]

                    start += 1

            end += 1

        curr_len = end - start
        max_len = max(max_len, curr_len)
        return max_len

Note:

• Time complexity = O(n), n is the length of the given string.
• Space complexity = O(n), n is the length of the given string.